快速求组合数可以用组合数公式或说杨辉三角:
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 ans=1; n%=MOD; while(m>0){ if(m&1) ans=(ans*n)%MOD; n=(n*n)%MOD; m>>=1; } return ans; } int _ca(ll n,ll m){ if(n<m) return 0; ll ans=1; for(int i=1;i<=m;i++){ ans=ans*((n+i-m)%MOD*kpow(i,MOD-2)%MOD)%MOD; } return ans; } // n=m=E(p^i*ai) // C(n,m)%MOD=II(C(ai,bi))%MOD int ca(ll n,ll m){ if(n<m) return 0; if(m==0) return 1; return _ca(n%MOD,m%MOD)*ca(n/MOD,m/MOD)%MOD; } int main(){ /////test C(n,m)%MOD //test Lucas Principle on http://blog.csdn.net/acdreamers/article/details/8037918 cout<<"ca(10,3):"<<ca(10,3)<<endl; cout<<"ca(10,0):"<<ca(10,0)<<endl; cout<<"ca(11,1):"<<ca(11,1)<<endl; cout<<"ca(1,1):"<<ca(1,1)<<endl; cout<<"ca(111111111111,1):"<<ca(111111111111,1)<<endl; cout<<"ca(111111111111,0):"<<ca(111111111111,0)<<endl; cout<<"ca(111111,111111):"<<ca(111111,111111)<<endl; cout<<"ca(111111,111110):"<<ca(111111,111110)<<endl; cout<<"ca(111111,111109):"<<ca(111111,111109)<<endl; cout<<"assert =:"<< (ll)111111*111110/2%MOD<<endl; cout<<"ca(111111,111112):"<<ca(111111,111112)<<endl; return 0; }