组合数 | 山暮云秋

递推求组合数

递推求组合数

1、组合数中有 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$ 。其中 $C_n^m$ 意为从 $n$ 个元素中选出 $m$ 个元素有多少种不同组合，其总的可能可划分为组合中选了第一个和组合中没选第一个两种。如果组合中选了第一个，那么剩下的方案数还有 $C_{n-1}^{m-1}$ 种(从剩余元素中选 $m-1$ 个)；如果组合中没选第一个，那么剩下的组合中还有 $C_{n-1}^m$ 种；这两种结果互斥，因此相加便可得到总的方案
2、这种方法运用了递推与DP的思想，上面的等式为状态转移方程。其中，$C_n^m$ 为新状态，通过方程将其转移为两个老状态的和。此外，需要确定起始点和边界：起始点为 $C_i^0 = 1$ (从任意多的元素中选 $0$ 个，有 $1$ 种方案——不选)；边界为 $C_i^j$ (其中 $0 \leq j \leq i$，$i \leq n$)

求组合数 1

1、求组合数 1：给定 $n$ 和 $m$ ($n,m \leq 1000$)，输出一个 $n \times m$ 的矩阵，矩阵下标从 $0$ 开始，矩阵的元素 $a[i][j] = C_i^j$ ，结果对 $10^9 + 7$ 取模
2、注意在对 $c[][]$ 初始化时，对于 $i=0$ 和 $j=0$ 都已被初始化，此外在进行状态转移时，需要注意边界($i \lt n$，$j \lt m$，$0 \leq j \leq i$)

代码实现

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
const int P = 1e9 + 7;

long long c[N][N];

void solve()
{
    int n, m;
    cin >> n >> m;
    // 初始化，C(i, 0) = 1
    for (int i = 0; i < n; i++)
        c[i][0] = 1LL;

    // 通过状态转移方程进行转移，C(i, j) = C(i - 1, j - 1) + C(i - 1, j)
    // 注意 i 边界，i < n
    for (int i = 1; i < n; i++)
        // 注意 j 边界，j <= i && j < m
        for (int j = 1; j <= i && j < m; j++)
            // 状态转移
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cout << c[i][j] << " ";
        cout << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

公式求组合数

公式求组合数

1、由计数原理中组合的公式可知 $C_n^m = \frac{n!}{(n-m)!m!}$ ，因此求 $C_n^m$ 需要求 $n!$、$(n-m)!$、$m!$ 这三种阶乘
2、由于数据通常较大，题目中常会要求结果对 $P$ 取模，此时对上面公式取模，可以通过乘法逆元将模运算的除法转换为模运算的乘法。因此 $C_n^m$ 在 $\pmod p$ 意义下可等于 $n! * ((n-m)!)^{-1} * (m!)^{-1} \bmod P$ ，其中 $x^{-1}$ 表示 $x$ 在 $\pmod p$ 意义下的乘法逆元，进而可等于 $n! * ((n-m)! * m! \bmod p)^{-1} \bmod p$
3、因此在实现中，可以先提前用数组 $fac[]$ 记录阶乘(阶乘可以递推得到，$fac[i] = fac[i-1] * i$)，再通过求逆元的方法得到逆元，最后用 $\pmod P$ 意义下的公式计算组合数
求组合数 2

1、求组合数 2：有 $q$ 次询问，每次给出 $n$ 和 $m$，输出 $C_n^m$ 的值。其中 $q \leq 10^5$ ，$n,m \leq 10^7$ ，结果对 $10^9 + 7$ 取模
2、由于题目的数据范围较大，且数据较离散，先前的递推法会耗费大量时间，应使用公式法。注意到模数是质数，所以通过费马小定理 + 快速幂来求逆元，再按照公式法求组合数(注意取模)

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e7 + 10; // 范围
const int P = 1e9 + 7;  // 模数

int fac[N]; // 记录阶乘

// 初始化阶乘数组 fac[]
void InitFac(int n)
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % P;
}

// 快速幂取模
int ModExp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}

// 求逆元：费马小定理 + 快速幂
int inv(int x)
{
    return ModExp(x, P - 2);
}

// 求组合数
int C(int n, int m)
{
    // 特判
    if (n < 0 || m < 0 || n < m)
        return 0;

    // 公式
    return fac[n] * inv(fac[n - m] * fac[m] % P) % P;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    cout << C(n, m) << '\n';
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    InitFac(1e7); // 初始化 fac[]

    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

线性求组合数

线性求组合数

1、求组合数-进阶：有 $q$ 次询问，每次需要求出 $C_n^m$ ，输出 $q$ 次询问的结果之和，结果对 $10^9 + 7$ 取模。输入 $q,a,b,c$ (且 $q,a,b,c \leq 10^7$)，再给出 $n_1$ 和 $m_1$ ，之后的询问按照 $(n_i, m_i) = (n_{i-1} * a + b,\ m_{i-1} * b + a) \bmod c$ 生成
2、在上题基础上，由于每次询问 $C_n^m$ 都需要求一次逆元，共需要 $O(n\log n)$ 的复杂度，因此可以提前预处理逆元并存入数组 $invfac[]$ ，即$invfac[i] = (i!)^{-1}$
3、由于 $invfac[i] = \frac{1}{i!}$ ，$invfac[i+1] = \frac{1}{(i+1)!} = \frac{1}{i! * (i+1)}$，所以存在状态转移方程：$invfac[i] = invfac[i+1] * (i+1)$ (分子乘上，和分母约分掉)。因此只需要计算最大的 $invfac[n]$ ，再通过转移方程线性递推即可得到 $invfac[]$ 。这样全程只需要求一次逆元，只需要 $O(n + log n) = O(n)$ 的复杂度

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e7 + 10; // 范围
const int P = 1e9 + 7;  // 模数

int fac[N];    // 记录阶乘
int invfac[N]; // 预处理逆元，存储 i! 的逆元

int inv(int x);

// 初始化阶乘数组 fac[]，预处理逆元
void InitFac(int n)
{
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = 1ll * fac[i - 1] * i % P;

    // 把 n! 的逆元存入 invfac[n]
    invfac[n] = inv(fac[n]);
    // 通过转移方程线性递推 invfac[]
    for (int i = n - 1; i >= 0; i--)
        invfac[i] = invfac[i + 1] * (i + 1) % P;
}

// 快速幂取模
int ModExp(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}

// 求逆元：费马小定理 + 快速幂
int inv(int x)
{
    return ModExp(x, P - 2);
}

// 求组合数
int C(int n, int m)
{
    // 特判
    if (n < 0 || m < 0 || n < m)
        return 0;

    // 公式，修改为通过 invfac[] 计算
    return fac[n] * invfac[n - m] % P * invfac[m] % P;
}

void solve()
{
    int q, a, b, c, n, m;
    cin >> q >> a >> b >> c >> n >> m;

    int sum = 0;
    // q 次询问
    for (int i = 1; i <= q; i++)
    {
        sum = (sum + C(n, m)) % P;

        // 准备下一次询问的 n, m
        n = (n * a + b) % c;
        m = (m * b + a) % c;
    }
    cout << sum;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    InitFac(1e7); // 初始化 fac[]

    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

递推求组合数

公式求组合数

线性求组合数

页底评论