算法-组合数的求法

一、基于动态规划思想的递推

当我们对组合数的转变关系进行分析时，可以得到一个关系（在j不等于0时）：

c
c[i][j] = c[i - 1][j] + c[i - 1][j - 1]

那么我们在求给定组合数之前，可以先进行初始化：

c
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;
}

在需要求哪个组合数时，对其进行查询即可

时间复杂度

时间主要在预处理阶段，对于组合数 $c_n^m$ ，时间复杂度是 $O(m*n)$

二、使用逆元进行预处理

已知组合数计算公式：

c_a^b = \frac{a！}{(a - b)！b！}

那么我们可以提前预处理出分子和分母的因子部分，在处以分母时，相当于乘上分母部分的逆元

因此，我们可以处理出分子与分母部分

886. 求组合数 II

完整代码如下：

c
#include<bits/stdc++.h>
using namespace std;

const int N = 100010, MOD = 1e9 + 7;


int fact[N], infact[N];
int n;

int qmi(int a, int b, int p)
{
    long long ans = 1;
    while(b)
    {
        if(b & 1) ans = (long long)ans * a % p;
        a = (long long)a * a % p;
        b >>= 1;
    }
    return ans;
}

int main()
{
    
    fact[0] = infact[0] = 1;
    for(int i = 1; i <= N; i ++)
    {
        fact[i] = (long long)fact[i - 1] * i % MOD;
        infact[i] = (long long)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD;
    }
    scanf("%d", &n);
    while(n --)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", (long long)fact[a] * infact[a - b] % MOD * infact[b] % MOD);
    }
    return 0;
}

时间复杂度：

在模MOD的情况下，每次快速幂的时间复杂度为 $O(log MOD)$ ，由于时间几乎都用在预处理阶段，因此综合来看时间复杂度为 $O(NlogMOD)$

问题：

由于该方法用到了快速幂求逆元，即费马小定理，因此要求MOD是质数，否则求逆元一步是不成立的

三、卢卡斯（Lucas）定理

C_a^b \equiv C_{a\mod p}^{b\mod p} * C_{a / p}^{b / p} \pmod{m}

887. 求组合数 III

有关证明这里不做赘述，具体的应用代码如下：

c
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int n;

int qmi(int a, int b, int p)
{
    LL ans = 1;
    while(b)
    {
        if(b & 1) ans = (LL) ans * a % p;
        a = (LL) a * a % p;
        b >>= 1;
    } 
    return ans;
}


int C(int a, int b, int p)
{
    if(b > a) return 0;
    
    int ans = 1;
    for(int i = 1, j = a; i <= b; i ++, j --)
    {
        ans = (LL) ans * j % p;
        ans = (LL) ans * qmi(i, p - 2, p) % p;
    }
    return ans;
}

int lucas(LL a, LL b, int p)
{
    if(a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; 
}

int main()
{
    scanf("%d", &n);
    while(n --)
    {
        LL a, b;
        int p;
        scanf("%lld %lld %d", &a, &b, &p);
        //cin >> a >> b >> p;
        printf("%d\n", lucas(a, b, p));
    }
    return 0;
}

需要高精度

888. 求组合数 IV

在一些情况下，如果结果不要求对某个质数取模，可能结果很大，需要用到高精度进行计算

tips：

由于在进行高精度运算时，同时使用乘法和除法需要大量的计算机性能，因此需要将除法转换为乘上逆元。
我们需要对公式上下的各结果进行因式分解，在对阶乘进行因式分解时，需要用到以下结论：

c++
#include<bits/stdc++.h>
using namespace std;

const int N = 5010;
int a, b;
int cnt;
int primes[N], sum[N];
bool st[N];

//筛质数
void prime(int n)
{
    if(n < 2) return;
    
    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 x, int y)
{
    int ans = 0;
    while(x)
    {
        ans += x / y;
        x /= y;
    }
    return ans;
}

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

int main()
{
    scanf("%d %d", &a, &b);
    prime(a);
    
    if(!b)
    {
        puts("1\n");
        return 0;
    }
    
    vector<int> ans;
    ans.push_back(1);
    
    for(int i = 0; i < cnt; i ++)
    {
        int p = primes[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);
    }
    
    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 --)
        printf("%d", ans[i]);
    
    puts("");
    
    return 0;
}