组合数学模板

快速幂

ll qpow(ll x, int n) {
    ll res = 1;
    while(n) {
        if(n&1) res = res * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return res;
}

组合数

void getC(int maxn) {
    C[0][0] = 1;
    for(int i=1; i<=maxn; i++) {
        C[i][0] = 1;
        for(int j=1; j<=i; j++) C[i][j] = C[i-1][j]+C[i-1][j-1];
    }
}

ll comb(int n,int m) {
    if(m>n) return 0;
    return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}

阶乘和逆元

ll fac[N],invfac[N],inv[N];
void init(int maxn) {
    fac[0]=invfac[0]=1;
    for(int i=1; i<=maxn; i++) fac[i]=fac[i-1]*i%mod;
    invfac[maxn]=qpow(fac[maxn],mod-2)%mod;
    for(int i=maxn-1;i>=0;i--) invfac[i]=invfac[i+1]*(i+1)%mod;
    inv[1]=1;
    for(int i=2;i<=maxn;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}

第一类斯特林数

把$n$个不同的元素构成$m$个圆排列的方案数，写作$s(n,m)$
递推式： $s(n,m)=s(n-1,m-1)+s(n-1,m)*(n-1)$

第二类斯特林数

把$n$个不同的球，放进$m$个相同的盒子，不能有空盒子的方案数，写作$S(n,m)$
递推式：$S(n,m)=S(n-1,m-1)+S(n-1,m)*m$

容斥原理快速求单项

ll sestl(int n,int m){
    ll ans=0;
    for(int i=0;i<=m;i++) ans=(ans+(i%2?-1:1)*comb(m,i)*qpow(m-i,n)%mod+mod)%mod;
    ans=ans*invfac[m]%mod;
    return ans;
}