题目链接

本题需要求出$C_{a}^{b}$的具体数值，而不是对p取模，所以要用到高精度

主要思路：

• $C_{a}^{b} = \frac{a!}{b!(a-b)!}$

• 将$C_{a}^{b}$按照右式分解质因数，求出每个质因数的个数
• 比如质因数p的次数就是 a!中的次数 - b!中的 - (a-b)!中的
• n! 中 p 的次数是 n/p + n/p^2 + n/p^3 + …
• 然后用高精度乘法累乘即可

#include <iostream>
#include <vector>
using namespace std;

const int NN = 5010;
int primes[NN], st[NN], num[NN];
int a, b, cnt;

// 得到1~n中所有的质数
void get_primes(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] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}

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

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



int main(){
    cin >> a >> b;

    get_primes(a);

    for (int i = 0; i < cnt; i ++){
        int p = primes[i];
        num[i] = get(a, p) - get(b, p) - get(a - b, p);
    }

    vector<int> res; res.push_back(1); // res 要记得初始化为1 !!!!
    for (int i = 0; i < cnt; i ++){
        for (int j = 0; j < num[i]; j ++){
            res = mul(res, primes[i]);   // 高精度
        }
    }

    for (int i = res.size() - 1; i >= 0; i --){  // 逆序输出
        cout << res[i];
    }

    return 0;
}