组合数模板

递归法求组合数

适用于

(C(a,b))，(a,b≤1000)，最终的答案对于一个质数取模

原理

从a个苹果中挑出来b个分两种情况

1.取苹果x(x是编号)，那么方案数是(C(a-1,b-1))

2.不取苹果x，那么方案数是(C(a,b-1))

总的方案数(C(a,b)=C(a-1,b-1)+C(a,b-1))

模板

int f[N][N];
for(int i=0;i<N;++i){
    for(int j=0;j<N&&j<=i;++j){
        if(!j) f[i][j]=1;
        else (f[i][j]=f[i-1][j]+f[i-1][j-1])%=mod;
    }
}

预处理逆元打表求

适用于

需频繁求(C(a,b))，(a,b≤1e6)，最终的答案对于一个质数取模

原理

(C(a,b) = a!/ (b!*(a-b)!) = a!*inv(b!)*inv((a-b)!))

模板

const int N=1000010,mod=1e9+7;
typedef long long LL;
int d[N];
int fac[N];
int inv[N];
inline int C(int n,int m){
    if(m>n)
        return 0;
    return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}

void init(){
    fac[0]=1;
    for(int i=1; i<N; i++)
        fac[i]=(LL)fac[i-1]*i%mod;
    inv[N-1]=qmi(fac[N-1],mod-2);
    for(int i=N-2; i>=0; i--)
        inv[i]=(LL)inv[i+1]*(i+1)%mod;
}

卢卡斯定理

适用于

求解(C(a,b)%p)，(a,b>1e8)，最终的答案对于一个质数取模

原理

若p是质数，则对于任意整数(1 ≤ b ≤ a)，有：
(C(a , b)=C( a\%p , b\%p )*C( a/p , b/p )(modp))

模板

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

分解质因子

适用于

求答案的具体值，或是对于一个非质数取模

原理

先筛出1~a的所有质数

由：(C(a,b) = a!/ (b!*(a-b)!))

然后对阶乘分解质因子，求所有质因子在：(a!,b!,(a-b)!)出现的次数，答案中每个质因子出现的次数就是(s_{a!}-s_{b!}-s_{(a-b)!})

枚举所有质因子用快速幂求解(s一般不会很大，可以直接暴力)。

模板

普通版：

const int N=2000010;
typedef long long LL;
int st[N],primes[N],tot,n,p,sum[N];
void get_primes(){
    for(int i=2;i<N;++i){
        if(!st[i]) primes[++tot]=i;
        for(int j=1;primes[j]*i<N;++j){
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;
        }
    }
}
int get(int a,int b){
    int s=0;
    while(a) s+=a/b,a/=b;
    return s;
}
LL qmi(int a,int b){
    int res=1;
    while(b) {
        if(b&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}
LL C(int a,int b){
    for(int i=1;i<=tot;++i){
        int prime=primes[i];
        sum[i]=get(a,prime)-get(b,prime)-get(a-b,prime);
    }
    LL res=1;
    for(int i=1;i<=tot;++i){
        res=(res*qmi(primes[i],sum[i]))%p;
    }
    return res;
}

高精度

int st[N],prime[N],tot,sum[N],a[N],b[N],ans[N];
void get_Prime(){
    for(int i=2;i<N;++i){
        if(!st[i]) prime[++tot]=i;
        for(int j=1;prime[j]<=N/i;++j){
            st[prime[j]*i]=1;
            if(!(i%prime[j])) break;
        }
    }
}
int calc(int x,int y){
    int cnt=0;
    while(x){
        cnt+=x/y;
        x/=y;
    }
    return cnt;
}
void mul(int arr[],int b){
    for(int i=0;i<N;++i){
        arr[i]*=b;
        if(i>0)
        arr[i]+=arr[i-1]/10,arr[i-1]%=10;
    }
}
void solve(int arr[],int a,int b){
    for(int i=1;i<=tot;++i){
        int p=prime[i];
        sum[i]=calc(a,p)-calc(b,p)-calc(a-b,p);
    }
    arr[0]=1;
    for(int i=1;i<=tot;++i){ 
        for(int j=1;j<=sum[i];++j){  //可以改成快速幂
            mul(arr,prime[i]);
        }
    }
}
void print(int arr[]){
    int i=N-1;
    while(arr[i]==0&&i>=0) --i;
    while(i>=0) cout<<arr[i--];
    puts("");
}