M27217: 有多少种合法的出栈顺序

http://cs101.openjudge.cn/practice/27217/

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

vector<int> ans = {1};
vector<int> prime;
int n, m, expo[1000], num;
bool b[2001];

vector<int> multiply(const vector<int>& ans, int x) {
    vector<int> c;
    int carry = 0;
    for (int i = 0; i < ans.size() || carry; i++) {
        if (i < ans.size()) carry += ans[i] * x;
        c.push_back(carry % 10);
        carry /= 10;
    }
    return c;
}

// 计算 n! 中质数 p 的指数（勒让德公式）
int getExponent(int n, int p) {
    int count = 0;
    while (n > 0) {
        n /= p;
        count += n;
    }
    return count;
}

int main() {
    scanf("%d", &n);
    
    // 筛法求素数
    memset(b, true, sizeof(b));
    for (int i = 2; i <= n * 2; i++) {
        if (b[i]) {
            prime.push_back(i);
            for (int j = i * i; j <= n * 2; j += i) {
                b[j] = false;
            }
        }
    }
    m = prime.size();
    
    // 计算卡特兰数的质因数分解
    // C_n = (2n)! / (n! * (n+1)!)
    for (int i = 0; i < m; i++) {
        int p = prime[i];
        // 分子：(2n)!
        expo[i] += getExponent(2 * n, p);
        // 分母：n! 和 (n+1)!
        expo[i] -= getExponent(n, p);
        expo[i] -= getExponent(n + 1, p);
    }
    
    // 根据质因数分解计算结果
    for (int i = 0; i < m; i++) {
        for (int j = 1; j <= expo[i]; j++) {
            ans = multiply(ans, prime[i]);
        }
    }
    
    // 输出结果
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d", ans[i]);
    }
    return 0;
}