求解组合数
注意maxm的范围为C(n,m)中，n+m的最大取值。。。
int facinv[maxm + 10], fac[maxm + 10];
ll qpow(int b, int p, int k) {
ll ans = 1, base = b;
while(p) {
if(p & 1) ans = ans * base % k;
p >>= 1;
base = base * base % k;
}
return ans % k;
}
ll C(ll n, ll m) {
if(n < m) return 1;
if(m*2>=n) m=n-m;
return (ll)fac[n] * facinv[m] % mod * facinv[n - m] % mod;
}
facinv[0] = fac[0] = 1;
for(int i = 1; i <= maxm; i++)
fac[i] = (ll)fac[i - 1] * i % mod;
for(int i = 1; i <= maxm; i++){
facinv[i] = facinv[i - 1] * qpow(i, mod - 2, mod)%mod;
}
组合数递推公式 \(C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}\)
递推预处理组合数
void pre(){
for(int i=1;i<=1000;++i){
c[i][i]=c[i][0]=1;
for(int j=1;j<i;++j){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
return ;
}
相关资料
求解组合数C(n,m)
https://blog.csdn.net/ZengAMing/article/details/63681754