1.递推法(杨辉三角)
从 n个数不同的数中选出 m个的方案数是 ,对第一个数有选和不选两种决策,若不选,则从剩下的 n-1个中选 m个,即
;若选,则从剩下的 n-1个中选 m-1个,即
。
所以递推式 =
+
根据公式我们发现和杨辉三角一样,
当n==1,m=0时,为1;当n==3,m==2时,为3。m,n数据小的时候我们可以用递推,但如果数据范围太大就要用其他方法
void getc(){
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
if(j==0)
a[i][j]=1; //数组a存储的是n=i,m=j的组合数
else{
a[i][j]=(a[i-1][j]+a[i-1][j-1])%mod;
}
}
}
}
2.快速幂+乘法逆元
因为组合数太大,算法竞赛中常见问题是求解组合数取模%p(其中p为质数),
=
在取模的条件下,除以一个数等价于乘以这个数的乘法逆元,例如,x /2%107=x*54%107,那么54就是 2在模107条件下的乘法逆元
1.求阶乘,求出n!,m!,(n-m)! %p,for循环递推即可,每次乘法后取模
2.求出m!,(n-m)! 的乘法逆元(%p),因为p为质数,所以 x的逆元即 ,用快速幂即可求出
易得,=a[n] * (a[n]的逆元)*(a[n-m]的逆元),总时间复杂度为O(n)
ll qpow(ll y,int z,int p){
ll ans=1;
while(y){
if(y&1)
ans*=y%p;
y=y*y%p;
y>>=1;
}
return ans;
}
long long c(long long n,long long m){
if(m>n)
return 0;
return ((a[n]*qpow(a[m],p-2,p))%p*qpow(a[n-m],p-2,p)%p);
//a[x]为递推求得的x的阶乘
}
3.卢卡斯定理
前半部分可以继续使用卢卡斯定理递归求解,后半部分可以用第二种方法直接求解,后半部分的m,n都会小于p,时间复杂度为O(n)。适用于n较大,p较小或n较小的情况
long long lucas(long long n,long long m){
if(!m) //也就是m>0
return 1;
return lucas(n/p,m/p)*c(n%p,m%p)%p; //前半部分为递归,后半部分 c为方法二中的函数
}