- 快速幂求组合数
- 大致描述:
就是对直接预处理出阶乘和阶乘的逆元,然后根据组合数的定义直接算就可以了,然后写的时候要注意开longlong,已经错过很多次了。很好理解。 - 板子:
- 大致描述:
点击查看代码
ll qpow(ll a,ll b) {
ll res = 1;
while(b) {
if(b&1) res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res;
}
ll C(int n,int m) {
if(m > n) return 0;
return (fact[n]*inv[m]%mod*inv[n - m]%mod);
}
void init() {
inv[0] = 1,fact[0] = 1;
for(int i = 1; i <= 500; i++)
fact[i] = fact[i - 1]*i%mod;
inv[500] = qpow(fact[500],mod - 2);
for(int i = 499; i >= 1; i--)
inv[i] = inv[i + 1]*(i + 1)%mod;
}