火车进栈
（卡特兰数+位压高精）
[题目](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;
}