卡塔兰long long

1.mod 我们用递推式用加法避免除和mod

include <bits/stdc++.h>
using namespace std;
long long dp[105];
long long f(int x)
{
if(dp[x]!=-1) return dp[x];
dp[x]=0;//归0
for(int i=0;i<x;i++)
{
dp[x]=(dp[x]+f(i)*f(x-1-i))%mod;//递推式
}
return dp[x];
}
int main()
{
int n;
while(cin>>n)
{
if(n==-1) break;
memset(dp,-1,sizeof(dp));
dp[0]=1;
cout<<f(n)<<endl;
}
}

2.公式的（用于不mod)

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

long long dp[105];
long long f(int x)
{
if(dp[x]!=-1) return dp[x];
return dp[x]=f(x-1)(4x-2)/(x+1);//先*避免出现整除
}
int main()
{
int n;
while(cin>>n)
{
if(n==-1) break;
memset(dp,-1,sizeof(dp));
dp[0]=1;
cout<<f(n)<<endl;
}
}