组合数模板
复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| const int N=2e6;
int Pow(int a,int b) {
int c=1;
while(b) {
if(b&1)c=(1ll*c*a)%mod;
a=1ll*a*a%mod;
b>>=1;
}
return c;
}
int C(int n,int m) {
if(n<m||m<0)return 0;
return fac[n]*infac[n-m]%mod*infac[m]%mod;
}
void init() {
fac[0]=1;
for(int i=1; i<N; i++)fac[i]=1ll*fac[i-1]*i%mod;
infac[N-1]=Pow(fac[N-1],mod-2);
for(int i=N-1; i>=1; i--)infac[i-1]=1ll*infac[i]*i%mod;
}
|