组合数取模

关于公式 C(n,m)=n!/m!(n-m)! 中带有除法,我们可以不能直接将n!和m!和(n-m)!直接取模再相除

所以这里需要求逆元,我们先预处理出每一个阶乘的逆元,然后再代入公式得:

C(n,m)=n!*ni(m)*ni(n-m) %mod ni[i]为i的逆元

求逆元可以用费马小定理,也可以用扩展欧几里得,扩展欧几里得可以参考这篇博客,费马小定理在该博客将给出结论

费马小定理:

假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

显然 ni(a)=a^(p-2)

 1 ll qm(ll x,ll k){   //快速幂
 2     if(k==0)return 1;
 3     ll sum=1;
 4     while(k){
 5         if(k&1)sum*=x,sum%=mod;
 6         k>>=1;x*=x;
 7         x%=mod;
 8     }
 9     return sum;
10 }
11 ll ni[N],f[N]; //fi为i的阶乘
12 void prework(){
13     f[0]=1;ni[0]=qm(f[0],mod-2);
14     for(int i=1;i<=n;i++){
15         f[i]=f[i-1]*i;f[i]%=mod;
16         ni[i]=qm(f[i],mod-2);
17     }
18 }

预处理出逆元那么就可以用上述公式O(1)求得组合数C(n,m)了

1 ll query(int n,int m){
2     ll ret=((f[n]*ni[m]%mod)*(ni[n-m]))%mod;
3     return ret;
4 }