ZTL — 数学 — 组合数

· · 个人记录

当模数（mod）足够大：

long long fact[maxn], finv[maxn];
inline void C_preprocess(int uplimit = maxn-7){
    fact[0] = fact[1] = 1;
    for(int i = 2; i <= uplimit; ++i)
        fact[i] = fact[i-1]*i % mod;
    finv[uplimit] = ksm(fact[uplimit], mod - 2);
    for(int i = uplimit-1; i >= 0; --i)
        finv[i] = finv[i+1]*(i+1) % mod;
}
inline long long C(int mm,int nn){
    if(mm < 0 || nn < 0 || mm < nn) return 0;
    return fact[mm] * finv[nn] % mod * finv[mm - nn] % mod;
}
注：C函数中的m,n对应到实际数学语言时为C_m^n，即从m个球中选n个的方案数,下同。

当模数（mod）较小，\exists \space n > mod或\exists \space m > mod：

由于这种时候经常要用Lucas定理，所以在此附带。

long long fact[maxn];
inline void C_preprocess(int uplimit = maxn-7){
    fact[0] = fact[1] = 1;
    for(int i = 2; i <= uplimit; ++i)
        fact[i] = fact[i-1]*i % mod;
}

inline long long C(int mm,int nn){
    if(mm < 0 || nn < 0 || mm < nn) return 0;
    //由于mod可能小于mm+nn，所以不能递推求逆元 
    return fact[mm] * ksm(fact[nn], mod-2)% mod * ksm(fact[mm-nn], mod-2) % mod;
}

long long Lucas(int mm, int nn){
    if(!nn) return 1;
    return C(mm%mod, nn%mod) * Lucas(mm/mod, nn/mod) % mod;
}