[数论]寻找组合数的四种方法

组合数的常用公式

零、纯暴力法

根据第一个公式，将的分子和分母求出，再相除即可。

适用范围：n，m较小的情况下。

时间复杂度：

第一种部分代码如下：

for(int i = n; i >= n - m + 1; i--)
    ans *= i;
for(int i = m; i >= 1; i--)
    ans /= i;

第二种部分代码如下：

fz = 1, fm = 1;    // fz表示分子，fm表示分母
for(int i = n, j = 1; j <= m; i--, j++){
    fz *= i;
    fm *= j;
}
ans = fz / fm;

一、杨辉三角法

上面的第三个公式是符合杨辉三角的公式，因此可以使用第三个公式进行预处理题目范围内所有的，需要时直接使用即可。

适用范围：n，m大小在左右。

时间复杂度：

C++部分代码如下：

// c[n][m]表示从n个元素中取m个的方案数
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];

二、预处理法

先预处理出范围内所有数的阶乘和阶乘逆元，根据第一个公式直接取需要的阶乘和阶乘逆元的值即可。

适用范围：n，m在以内，且取模的数mod为素数时。

时间复杂度：

乘法逆元的求法可以参照本人之前的博客：求逆元的四种方法_Wmiracle的博客-****博客

由于这里取模的数为素数，因此可以用费马小定理求逆元。

C++部分代码如下：

ll quick_pow(ll a, ll b){    // 快速幂
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void init(){    // 预处理，fac[]表示阶乘, inf[]表示阶乘的逆元
	fac[0] = inf[0] = 1;
	for(int i = 1; i <= N; i++){
		fac[i] = fac[i - 1] * i % mod;
		inf[i] = inf[i - 1] * quick_pow(i, mod - 2) % mod;
	}
}

// ans = fac[n] * inf[m] % mod * inf[n - m] % mod;

三、Lucas定理

Lucas定理简单来说是这样的：如果p是素数，对于任意整数，都有，其中可以再进行分解，直至n，m小于p为止。

更为标准的Lucas定理式为：

其中，

       。

适用范围：n，m较大但不超过（当然正常也不会超过），且p的数量级不超过时。

时间复杂度：

证明过程：因为p为素数，当时，都有，

                  于是就有

                                                

                  对比两边项的系数，结合二项式定理，                      得证。

C++部分代码如下：

ll quick_pow(ll a, ll b, int p){    // 快速幂
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

ll C(ll a, ll b, int p){    // 求组合数C(a, b)
    if(a < b) return 0;
    ll fz = 1, fm = 1;    // fz表示分子，fm表示分母
    for(int i = a, j = 1; j <= b; i--, j++){
        fz = fz * i % p;
        fm = fm * j % p;
    }
    return fz * quick_pow(fm, p - 2, p) % p;
    
}

ll Lucas(ll a, ll b, int p){    // Lucas定理
    if(a < p && b < p) return C(a, b, p);
    else return C(a % p, b % p, p) * Lucas(a / p, b / p, p) % p;
}

// ans = Lucas(n, m, p);

四、分解质因数法

分解质因数法是将分子分母的乘积写成质因数乘积，用数组储存指数，最后指数对应相减，剩下来的质因数相乘即为答案。

这里先给出结论，其中k为分解后质因数的个数。

适用范围：需要求的是组合数的真实值而并非取模值时。

证明过程：根据算术基本定理：任何大于1的自然数N，如果N不为质数，那么N可以唯一分解成有限个质数的乘积，即

由于中质因子p出现的次数

       中质因子p出现的次数

       中质因子p出现的次数

所以中质因子p出现的次数为

又

故一定可以转换成若干个质因数的乘积，且每个质因数出现的次数为

因此最终得证。

C++代码如下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 5005;
int primes[N], cnt;    // cnt[]存储所有素数，cnt表示统计分解成的素数的个数
int sum[N];    // sum[]存储每个素数的次数
bool st[N];    // st[]存储每个数是否被筛掉

void Euler_seive(int n){    // 欧拉筛法求素数
    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] = true;
            if(i % primes[j] == 0) break;   // 如果这个数能被素数整除，跳出循环
        }
    }
}

int get(int n, int p){    // 求n!中素数p出现的次数
    int res = 0;
    while(n){
        res += n / p;
        n /= p;
    }
    return res;
}

vector<int> mul(vector<int> a, int b){    // 高精度乘法
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size(); i++){
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t){
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main(){
    int n, m;
    cin >> n >> m;
    Euler_seive(n);
    for(int i = 0; i < cnt; i++){    // 求每个质因数出现的次数
        int p = primes[i];
        sum[i] = get(n, p) - get(m, p) - get(n - m, p);
    }
    vector<int> ans;
    ans.push_back(1);
    
    for(int i = 0; i < cnt; i++)    // 用高精度乘法将转换后所有剩下的质因数相乘
        for(int j = 0; j < sum[i]; j++)
            ans = mul(ans, primes[i]);
    
    for(int i = ans.size() - 1; i >= 0; i--)    // 输出答案
        cout << ans[i];
    cout << endl;
    return 0;
}