组合数

组合数"/>

组合数

部分内容参考博客[组合数]求组合数的几种方法总结

求C ( m, n ) % p;
组合数是数论中比较重要的一个内容，涉及到的内容主要有两个。组合数求解的式子中会很容易出现比较大的数和除法运算。因此，求组合数其实就是要解决这两个问题。解法主要有两种：（其实很多博主都还写了杨辉三角，不过其实用不到，我没写O(∩_∩)O哈哈~）
1.用逆元求解

C( m, n ) % p = m！/ (n! * (m - n )!) % p;因此，就算是化简后，依旧会出现分子和分母都很大的情况。
由于不能直接对他们取模后再除，因此我们可以用逆元的方法，把里面的除法运算转换成乘法运算，问题也就迎刃而解了^_。此时问题就转换了如何求逆元的问题。
请参考我的另一篇博客逆元求法

在此附上线性递推求组合数的代码，其他的方法也是一样的，不做累述

//对于单个情况
int inv(int a) { return a == 1 ? 1 : (MOD - MOD / a) * inv(MOD % a) % MOD;  
}  
int C(int m,int n)
{int ans1=1,ans2=1;if(n>m-n)n=m-n;for(int i=0;i<n;i++){ans2=ans2*(i+1)%MOD;ans1=ans1*(m-i)%MOD;}int x,y;return ans1*inv(ans2)%MOD;
}
//对于打表的代码
LL fact[maxn+5];
LL a[maxn+10];
LL inv[maxn+10];
void init(){a[0] = a[1] = 1;fact[0] = fact[1] = 1;inv[1] = 1;for(int i = 2; i <= 100005; i++){fact[i] = fact[i-1] * i % mod;inv[i] = (mod - mod/i)*inv[mod%i]%mod;a[i] = a[i-1] * inv[i] % mod;}
}LL C(int n, int m){return fact[n]*a[n-m]%mod*a[m]%mod;
}

2.lucas（卢卡斯）定理求解

此方法针对a，b均很大，而p很小的情况
定理叙述：如果p为素数，且a，b 为正整数并且a，b转换为p进制的数为
a = Ak p^k + Ak-1 p^k-1 + Ak-2 p^k-2 + … + A0;
b = Bk p^k + Bk-2 p^ k-1 + Bk-2 p^k-2 +… + B0;
则有公式C(a，b) = C(Ak,Bk) * C(Ak-1, Bk-1) * C(Ak-2, Bk-2) *… *C(A0,B0);
至于证明我专门查了查资料：

ps：一时不会也没关系，知道定理就行了。
转换后的递归方程为：C(n,m) % p = （C(n % p, m % p) * Lucas( n / p, m / p )) % p。（递归出口为m==0，return 1）
此时，我们就可以用lucas定理求逆元了。

int quick_power_mod(int a,int b,int m){//pow(a,b)%mint result = 1;int base = a;while(b>0){if(b & 1==1){result = (result*base) % m;}base = (base*base) %m;b>>=1;}return result;
}
//计算组合数取模
ll comp(ll a, ll b, int p) {if(a < b)   return 0;if(a == b)  return 1;if(b > a - b)   b = a - b;int ans = 1, ca = 1, cb = 1;for(ll i = 0; i < b; ++i) {ca = (ca * (a - i))%p;cb = (cb * (b - i))%p;}ans = (ca*quick_power_mod(cb, p - 2, p)) % p;return ans;
}
ll lucas(ll n, ll m, ll p) {ll ans = 1;while(n&&m&&ans) {ans = (ans*comp(n%p, m%p, p)) % p;n /= p;m /= p;}return ans;
}

其实单纯的lucas定理在做题是并非很经常用到（相反逆元用的更多），由于lucas定理是一个不断分解的情况，因此时间复杂度会很高。但是我们仔细想下，如果a和b过大，而且要求很多个这样的组合数，已经出超出了用逆元打表的范围，但是p又很小。这样我们就可以把方法一和方法二结合起来，我们可以用方法一打一个1到10^{6范围内的表，然后再用lucas定理把最初的a和b分解到这个表内，此时就很容易求出这样的组合数了，由于我感觉不常用，就不再附代码了。有兴趣的可以自己写下}_^