组合数

复习了一下数论（我好菜啊）
写一篇关于组合数的小结
以后应该有一篇容斥的小结

二项式定理

(a+b)n=∑i=0nCinan−ibi

证明：

求组合数

1.杨辉三角O（n^2）
2.乘法逆元
（1）扩展欧几里得
（2）费马小定理（模数为质数时）

因为

ap−1=1(modp)

所以

a∗ap−2=1(modp)

得a的乘法逆元为

ap−2

实现

ans=cnk

up=down=1;
for(int i=k-n+1;i<=k;i++)up=up*i%mod;
for(int i=n;i>=1;i--)down=down*i%mod;
ans=up*Qpow(down,mod-2)%mod;

3.Lucas定理（模数较小时）