【模板】组合数

posted on 2022-02-12 16:24:56 | under 模板 | source

$$C_n^m=\frac{n!}{m!(n-m)!}$$

LL qpow(LL a,LL b,int p=P){
    LL ans=1%p;
    for(;b;b>>=1,a=a*a%p) if(b&1) ans=ans*a%p;
    return ans;
}
template<int N> struct C_prime{
    LL fac[N+10],inv[N+10];int p;
    C_prime(int p=P):p(p){
        for(int i=fac[0]=inv[0]=1;i<=N;i++) fac[i]=fac[i-1]*i%p;
        inv[N]=qpow(fac[N],p-2,p);
        for(int i=N-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%p;
    }
    LL operator()(int n,int m){return fac[n]*inv[n-m]%p*inv[m]%p;}
};

原文地址：http://www.cnblogs.com/caijianhong/p/16863302.html