组合数的四种求法

大家好，欢迎来到IT知识分享网。

(这里写自定义目录标题)

一. 组合数的定义

• 公式：$C_a^b$=$\frac{a!}{(a-b)!\ast b!}$=$\frac{(a-b+1)\ast (a-b+2)\ast \dots .\ast a}{b!}$
• 使用情景：a较大，b较小
• 时间复杂度：O(b)
• 实现方法：先分别算出 分子和分母，然后利用求逆元算出最后的结果

int C(int a,int b) { 
    int up=1; int down=1; for(int i=a,j=1;j<=b;j++,i--) { 
    up=up*i%p; down=down*j%p; } ans=up*qmi(down,p-2); } 

二. 杨辉三角

• 公式：$C_a^b$=$C_{a-1}^b$+$C_{a-1}^{b-1}$
• 使用场景：a较小
• 时间复杂度：O($a^2$)
• 实现方法：递归打表

int C(int a,int b) { 
    for(int i=0;i<=a;i++) for(int j=0;j<=b&&j<=i;j++) if(!b) c[i][j]=1; else c[i][j]=c[i-1][j]+c[i-1][j-1]; } 

三. Lucas定理

• 公式：$C_a^b$=($C_{a/p}^{b/p}$+$C_{amodp}^{bmodp}$)%p
• 使用场景：用于以较快的速度计算很大的组合数。
• 时间复杂度：O($lo{g}_{n}p\ast p$)

int qmi(int a,int b) { 
    int result=1; while(b) { 
    if(b&1) result=result*a%p; b>>=1; a=(a*a)%p; } return result; } int C(int a,int b) { 
    int ans; int down=1,up=1; for(int i=1,j=a;i<=b;i++,j--) { 
    up=up*j%p; down=down*i%p; } ans=up*qmi(down,p-2); return ans; } int Lucas(int a,int b) { 
    if(a<p&&b<p) return C(a,b); return C(a%p,b%p)*Lucas(a/p,b/p)%p; } 

四：质因数分解

• 使用场景：需要求的是组合数的真实值而并非取模值时。

#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 5005; int primes[N], cnt; // cnt[]存储所有素数，cnt表示统计分解成的素数的个数 int sum[N]; // sum[]存储每个素数的次数 bool st[N]; // st[]存储每个数是否被筛掉 void Euler_seive(int n){ 
    // 欧拉筛法求素数 for(int i=2;i<=n;i++){ 
    if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<=n/i;j++){ 
    st[primes[j]*i]=true; if(i%primes[j] == 0) break; // 如果这个数能被素数整除，跳出循环 } } } int get(int n,int p){ 
    // 求n!中素数p出现的次数 int res=0; while(n){ 
    res+=n/p; n/=p; } return res; } vector<int> mul(vector<int> a,int b){ 
    // 高精度乘法 vector<int> c; int t=0; for(int i=0;i<a.size();i++){ 
    t+=a[i]*b; c.push_back(t%10); t/=10; } while(t){ 
    c.push_back(t%10); t/=10; } return c; } int main(){ 
    int n,m; cin>>n>>m; Euler_seive(n); for(int i=0;i<cnt;i++){ 
    // 求每个质因数出现的次数 int p=primes[i]; sum[i]=get(n,p)-get(m,p)-get(n-m,p); } vector<int> ans; ans.push_back(1); for(int i=0;i<cnt;i++) // 用高精度乘法将转换后所有剩下的质因数相乘 for(int j=0;j<sum[i];j++) ans=mul(ans,primes[i]); for(int i=ans.size()-1;i>=0;i--) // 输出答案 cout<<ans[i]; cout<<endl; return 0; }