快速求组合数可以用组合数公式或说杨辉三角:
C(n-1,m)+C(n-1,m-1)=C(n,m)
例如c3,0+c3,1=c4,1 c3,1+c3,2=c4,2
从c1,0 c1,1开始往后推
int a[n][n];// c(1,1) => c(n-1,n-1)
a[1][0]=a[1][1]=1;
for(int i=2;i<n;i++)
for(int j=0;j<=i;j++){
if(j==0) a[i][j]=1;
else a[i][j]=a[i-1][j]+a[i-1][j-1];
}
LUCAS定理:
n=E(ai*p^i), m=E(bi*p^i)
c(n,m)%p=II (c(ai,bi) ) %p
注意,c(ai,bi)%p=II(ai+i-bi)/i = II(ai+i-bi) * (i^(p-2)) %p
m^n 可以用快速乘方运算求得。
int kpow(ll n,ll m){
ll ......
阅读全文