卡特兰数

https://zhuanlan.zhihu.com/p/31317307

火车进出栈问题
和腾讯那道猜拳游戏是一样的

坑的地方：要把最大质数设为12万，因为卡特兰数中有2*n
用到的模板：求素数模板，求n!的模板，高精度模板，高精度可以压位

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

const int N = 120010;
bool seen[N];

vector<int> get_prime(int n){
    vector<int> prime;
    for(int i=2;i<n;i++){
        if(!seen[i]){
            prime.push_back(i);
        }
        
        for(int j=i;j<n;j+=i){
            seen[j] = true;
        }
    }
    return prime;
}


int get(int n,int p){
    int cnt = 0;
    while(n){
        cnt += n/p;
        n /= p;
    }
    return cnt;
}

void multi(vector<int>& res,int x){
    
    int c = 0;
    for(int i = 0;i<res.size();i++){
        res[i] = x * res[i] +c;
        c = res[i]/10000;
        res[i] = res[i]%10000;
    }
    while(c){
        res.push_back(c%10000);
        c/=10000;
    }
}

void out(vector<int> res){
    printf("%d",res.back());
    for(int i=res.size()-2;i>=0;i--) printf("%04d",res[i]);
    cout<<endl;
}


int main(){
    int n;
    cin>>n;
    vector<int> prime = get_prime(N);
    vector<int> power(N,0);
    long long ans = 1;
    
    for(int i=0;i<prime.size();i++){
        int p = prime[i];
        power[i] = get(2*n,p)-2*get(n,p);
    }
    
    int k = n+1;
    for(int i=0;prime[i]<=k;i++){
        int cnt = 0;
        int p = prime[i];
        while(k%p==0){
            k = k / p;
            cnt++;
        }
        power[i]-=cnt;
    }
    //while(power.size()&&power.back()==0) power.pop_back();
    
    // for(int i=0;i<power.size();i++){
    //     if(power[i]!=0)
    //         cout<<power[i]<<endl;
    // }
    
    vector<int> res;
    res.push_back(1);
    for(int i=0;i<=N;i++){
        while(power[i]--)
            multi(res,prime[i]);
        
    }

    out(res);
    return 0;
}