求 \(C_{n}^{k}\%p\)(p 为质数)
\[C_{n}^{k}=\frac{n!}{k!(n-k)!}\]
设 \(n!=a_1p^{e_1}, k!=a_2p^{e_2}, (n-k)!=a_3p^{e_3}\)
如果 \(e_1-(e_2+e_3)>0\), 则 \(C_{n}^{k}\%p=0\)
否则 \(C_{n}^{k}\%p=\frac{a_1}{a_2a_3}\%p=a_1(a_2a_3)^{(p-2)}\%p\)(费马小定理)
- LL mod_fact(LL n, LL p, LL &e)
- {
- if (n<=1) return 1;
- LL ret=mod_fact(n/p, p, e);
- e+=n/p;
- if ((n/p) & 1) return ret*(fact[n%p]*(p-1)%p)%p;
- else return ret*fact[n%p]%p;
- /* (p-1)!=-1(mod p) */
- }
- LL calc_C(LL n, LL k, LL p)
- {
- LL e1=0, e2=0, e3=0;
- LL a1=mod_fact(n, p, e1);
- LL a2=mod_fact(k, p, e2);
- LL a3=mod_fact(n-k, p, e3);
- if (e1-(e2+e3)>0) return 0;
- return (a1*POW(a2*a3%p, p-2, p)%p);
- }
来源: http://www.bubuko.com/infodetail-2515832.html