组合数求解方法（迭代乘法，dp，逆元，卢卡斯）

今天打乐扣周赛，t4被组合数溢出卡了。后面换了py才过。痛定思痛，出一期求解组合数，几种推导方法如下

直接计算

适用范围：n <= 10

   long long fact(int n) {
       long long res = 1;
       for (int i = 2; i <= n; ++i)
           res *= i;
       return res;
   }
   long long nCk(int n, int k) {
       return fact(n) / (fact(k) * fact(n - k));
   }

迭代乘法

适用范围： n <= 15和m <= 15

如果把/i改成逆元，可以搞到更大

ll C(ll n, ll m, ll p){
    ll res = 1;
    for (int i = 1; i <= m; ++i)
        res = res * (n - i + 1) / i;//为什么这里可以保证整除，因为范围区间i里面肯定有一个整数是i的倍数，可以从n%i < i来理解
    return res % p;
}

//逆元优化（如果你不用逆元，除法取模影响结果）
res = (res * (n - i + 1) % p) % p * inv[i] % p; 

动态规划

适用范围：n <= 1000

cpp

   int C[1001][1001];
   void calculateCombinations() {
       for (int i = 0; i <= 1000; ++i) {
           C[i][0] = C[i][i] = 1;
           for (int j = 1; j < i; ++j)
               C[i][j] = C[i-1][j-1] + C[i-1][j];
       }
   }
   
   int nCk(int n, int k) {
       return C[n][k];
   }

阶乘逆元

如果要取模的话，用预处理阶乘+逆元和卢卡斯定理

先预处理出逆元，f[x]存x！(mod p)，g[x]存(x!)^-1(mod p)。

前提是p为质数，并且n,m都与p互质。

C(n,m) (mod p) = f[n] * g[n-m] * g[m] (mod p);直接按最基础的公式推出来的

注意此处求的x都是阶乘，直接用递推求逆效率较低，有如下公式推导

$$\frac{1}{i!}(\mathrm{mod}p)=\frac{1}{i}\times \frac{1}{(i-1)!}(\mathrm{mod}p)=\mathrm{qpow}(i,p-2)\ast g[i-1]$$

1/i是i的逆元，你可以开局预处理完所有的，这里直接用的费马小定理求

如果求单个的话，直接迭代乘法加逆元更好。

卢卡斯

$$C_n^m=C_{\frac{n}{p}}^{\frac{m}{p}}\ast C_{nmodp}^{mmodp}(modp)$$

p为质数，可以迭代下去

ll qpow(ll x, ll y){
    ll res = 1;
    while(y){
        if(y & 1) res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res;
}
void init(){
    f[0] = g[0] = 1;
    for(int i = 1; i < N; i++){
        f[i] = f[i-1] * i % p;
        g[i] = g[i-1] * qpow(i, p-2) % p;
    }
}
ll C(ll n, ll m){ //用的是阶乘逆元方法
    if(n < m) return 0; //注意这里比较容易RE
    return f[n] * g[m] * g[n-m] % p;
}
ll Lucas(ll n, ll m){
    if(m == 0) return 1;
    return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}

原文地址：https://blog.csdn.net/2301_79199219/article/details/140620839

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！