一、递推法[杨辉三角法]
组合数满足递推关系\(C(n, k) = C(n-1, k-1) + C(n-1, k)\)。因此，可以使用递推法计算组合数。这种方法需要预处理\(C(0, 0) = 1\)和\(C(n, 0) = 1\)以及\(C(n, n) = 1\)的边界情况，然后使用递推公式计算出其他组合数的值。
杨辉三角是一种三角形数表，其中每个数等于它上方两数之和。杨辉三角的第n行中的第k个数就是组合数C(n-1, k-1)。因此，可以使用杨辉三角来计算组合数。
特点：
- 时间复杂度\(O(T ^ 2)\)【T为询问次数】
- 递推[DP] + 注意边界处理
- 取模
点击查看代码
void init(){
for(int i = 0; i < N; i ++){
for(int j = 0; j <= i; j ++){
if(!j)C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}
二、阶乘逆元法
阶乘逆元法是一种用于计算组合数模质数的方法。该方法使用费马小定理，将求组合数的问题转化为求阶乘逆元的问题。具体来说，如果mod是质数，那么可以先预处理出1到mod-1的阶乘逆元，然后使用这些逆元来计算组合数模mod的值。
特点：
- 时间复杂度\(O(TlogT)\)【T为询问次数】
- 预处理出阶乘和阶乘的逆元
- 公式法求组合数 + 快速幂求逆元 + 边界处理
- 取模,模一般为大质数[互质条件]
点击查看代码
typedef long long LL;
const int N = 1e5 + 10,mod = 1e9 + 7;
LL fact[N],infact[N];
LL qmi(LL a,LL k){
LL res = 1;
while(k){
if(k & 1)res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
void init(){
fact[0] = infact[0] = 1;
for(int i = 1; i < N; i ++){
fact[i] = fact[i - 1] * i % mod;
infact[i] = qmi(fact[i], mod - 2) % mod; //快速幂求逆元
}
}
//fact[a] * infact[b] % mod * infact[a - b] % mod
三、Lucas定理
Lucas定理是一个用于计算组合数模质数的定理。该定理指出，如果p是质数，n和k是非负整数，那么C(n, k)模p的值等于\(C(n\ mod\ p, k\ mod\ p)\)和\(C(n/p, k/p)\ mod\ p\)的值的乘积模p的值。Lucas定理的优点是可以避免数据溢出，并且可以使用较小的质数求解问题。
特点：
- 时间复杂度\(O(plogNlogp)\)【p为mod,N为组合数下标】
- 取模数小，组合数下标和上标n,k大
- lucas递归 + 定义循环求组合数 + 快速幂逆元
点击查看代码
typedef long long LL;
LL qmi(LL a,LL k,LL p){
LL res = 1;
while(k){
if(k & 1)res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
LL C(LL n,LL k,LL p){
LL res = 1;
for(int i = n,j = 1; j <= k; i --,j ++ ){
res = res * i % p;
res = res * qmi(j,p - 2,p) % p;
}
return res;
}
LL lucas(LL n,LL k,LL p){
if(n < p && k < p)return C(n,k,p);
else return C(n % p,k % p,p) * lucas(n/p,k/p,p) % p;
}
//lucas(n,k,p) << '\n';
四、高精度组合数
特点：
- 分解质因数 + 高精度乘法
- 不取模
- 阶乘里有多少个某个因子
点击查看代码
#include<iostream>
#include<vector>
using namespace std;
typedef vector<int> VI;
const int N = 5010;
int primes[N],sum[N],cnt;
bool st[N];
void get_primes(){
for(int i = 2; i < N; i ++){
if(!st[i])primes[cnt++] = i;
for(int j = 0;primes[j] <= N / i; j ++){
st[primes[j] * i] = 1;
if(i % primes[j] == 0)break;
}
}
}
int get(int n,int p){
int res = 0;
while(n){
res += n / p;
n /= p;
}
return res;
}
VI mul(VI A,int b){
VI res;
int t = 0;
for(int i = 0; i <= A.size() -1 || t; i ++){
if(i <= A.size() - 1)t += A[i] * b;
res.push_back(t%10);
t /= 10;
}
while(res.size() > 1 && res.back() == 0)res.pop_back();
return res;
}
int main(){
int a,b;
cin >> a >> b;
get_primes();
for(int i = 0; i < cnt; i ++){
int p = primes[i];
sum[i] = get(a,p) - get(b,p) -get(a-b,p);
}
VI res;
res.push_back(1);
for(int i = 0 ;i <cnt; i ++){
int p = primes[i];
for(int j = 0; j < sum[i] ; j ++){
res = mul(res,p);
}
}
for(int i =res.size()-1; i>=0; i --)cout << res[i];
return 0;
}