递推求组合数


  • 递推求组合数

    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 <= j <= i,i <= n)

  • 求组合数 1

    1、求组合数 1:给定 n 和 m(不超过 1000),输出一个 n*m 的矩阵,矩阵下标从 0 开始,矩阵的元素a[i][j] = C(i, j),结果对 109 + 7 取模
    2、注意在对c[][]初始化时,对于 i=0j=0已被初始化,此外在进行状态转移时,需要注意边界(i < n,j < m,0 <= j <= 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) = n! / ((n-m)! * m!),因此求C(n, m)需要求n!(n-m)!m!三种阶乘
    2、由于数据通常较大,题目中常会要求结果对 P 取模,此时对上面公式取模,可以通过乘法逆元模运算的除法转换为模运算的乘法。因此C(n, m) % P模 P 意义下可等于n! * inv[(n-m)!] * inv[m!] % P,其中inv[x]表示 x 在模 P 意义下乘法逆元,进而可等于n! * inv[(n-m)! * m! % P] % P
    3、因此在实现中,可以先提前用数组fac[]记录阶乘(阶乘可以递推得到,fac[i] = fac[i-1] * i),再通过求逆元的方法得到逆元,最后用模 P 意义下的公式计算组合数

  • 求组合数 2

    1、求组合数 2:有 q 次询问,每次给出 n 和 m,输出C(n, m)的值。其中 q 不超过 105,n 和 m 不超过 107,结果对 109 + 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 次询问的结果之和,结果对 109 + 7 取模。输入 q,a,b,c(不超过 107),再给出n[1]m[1]之后的询问按照(n[i], m[i]) = (n[i-1] * a + b, m[i-1] * b + a) % c生成
    2、在上题基础上,由于每次询问C(n, m)都需要求一次逆元,共需要 O(n * log n) 的复杂度,因此可以提前预处理逆元存入数组invfac[](即invfac[i]存储 i! 的逆元)
    3、由于invfac[i] = 1 / (i!)invfac[i+1] = 1 / ((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;
    }

页底评论