数学基础

常用计数预处理:阶乘,逆元,组合数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
namespace Math
{
    int fac[MAX],inv[MAX],C[MAX][MAX];
    inline void init(int N)
    {
        fac[0]=1; for(int i=1;i<=N;++i) fac[i]=Cmul(fac[i-1],i);
        inv[N]=qpow(fac[N],Mod-2); for(int i=N-1;i;--i) inv[i]=Cmul(inv[i+1],i+1);
        C[0][0]=1;
        for(int i=1;i<=N;++i)
        {
            for(int j=1;j<=N;++j) C[i][j]=Cadd(C[i-1][j-1],C[i-1][j]);
            C[i][0]=1;
        }
    }
}