火车进栈 （卡特兰数+位压高精）

火车进栈

（卡特兰数+位压高精）

[题目](130. 火车进出栈问题 - AcWing题库)

思路：车厢进出栈视为\(01\)序列,则每种\(01\)序列对应一种出栈顺序，答案即为：\({\Large \frac{1}{n+1} C_{2n}^{n}}\)

数据范围：\(1{\Large \le }n{\Large \le }60000\)（数据开到\(2n\),因为这个卡了一小时qwq

考虑对\(n!\)进行质因数分解，用位压高精度计算，注意输出时补\(0\)

#pragma GCC optimize(3) 
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N=1.2e5+10;
const LL base=1e12;//位压基准

int n,idx,pri[N];
bool st[N];
vector<LL> ans;

void mul(vector<int> &A,int b)
{
    LL t=0;
    for(int i=0;i<A.size();++i)
    {
        t+=A[i]*b;
        A[i]=t%base;
        t/=base;
    }
    while(t) {A.push_back(t%base);t/=base;}
}

void get_pri(int n)//线性筛
{
    for(int i=2;i<=n;++i)
    {
        if(!st[i]) pri[idx++]=i;
        for(int j=0;pri[j]<=n/i;++j)
        {
            st[pri[j]*i]=1;
            if(i%pri[j]==0) break;
        }
    }
}

int pri_num(int x,int p)//求n！中p因数个数
{
    int res=0;
    while(x)
    {
        res+=x/p;
        x/=p;
    }
    return res;
}

signed main()
{
    cin>>n;
    get_pri(n*2);
    
    ans.push_back(1);
    for(int i=0;i<idx;++i)
    {
        int num=pri_num(2*n,pri[i])-pri_num(n,pri[i])*2;
        int t=n+1;
        while(t%pri[i]==0) {num--;t/=pri[i];}
        while(num--) mul(ans,pri[i]);
    }
    cout<<ans.back();
    for(int i=ans.size()-2;i>=0;--i)
        printf("%012lld",ans[i]);
    return 0;
}