计算精确组合数代码模板

思路：考虑$C(n, m) = \frac{n!}{m!(n - m)!}$，我们求出这个表达式中所有的素因子的个数，然后用高精度乘起来即可

统计$n!$包含因数$p$的次数，朴素的做法是，枚举$1$到$n$，分别求他们的$p$的幂次，然后求和

在这里我们没有使用这种方法，而是按照幂次由低到高统计的

$$ p(n!) = [\frac{n}{p}] + [\frac{n}{p^2}] + … + [\frac{n}{p^{k}}] $$

其中，$p^k \leq n < p^{k + 1}$

简单用几句话粗糙地证明一下：$1$到$n$中，有$[\frac{n}{p}]$个数能够被$p$整除，有$[\frac{n}{p^2}]$个数能够被$p^2$整除……这样下去，只要把统计结果直接加起来，就是$p$在$n!$中的次数了

在代码实现的时候，由于统计的是$n/p,n/p/p,n/p/p/p…$的和，所以可以边统计边直接让n /= p

另外还从y总那里学到了一种比较简洁的低精度乘高精度模板

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 9;

int prime[N], cnt, sum[N];
bool judge[N];

void getPrime() {
    for (int i = 2; i < N; i++) {
        if (!judge[i]) {
            prime[cnt++] = i; 
        }
        for (int j = 0; j < cnt && (i * prime[j] < N); j++) {
            judge[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}

int getCnt(int n, int p) { //n! % (p ^ ret) == 0 
    int ret = 0;
    while (n) {
        ret += n / p;
        n /= p;
    }
    return ret;
}

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

void calc(int n, int m) {
    getPrime();
    if (n < m) {
        swap(n, m);
    }
    for (int i = 0; i < cnt; i++) {
        sum[i] = getCnt(n, prime[i]) - getCnt(m, prime[i]) - getCnt(n - m, prime[i]);
    }
    vector<int> res;
    res.push_back(1);
    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j < sum[i]; j++) {
            res = mul(res, prime[i]);
        }
    }
    for (int i = res.size() - 1; i >= 0; i--) {
        printf("%d", res[i]);
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    calc(n, m);
    return 0;
}