正题

      一看到输入3，输出5，我们就可以想到Catalan数，但是要详细说明一下。

      因为每次可以从n个角中选取一个角，将他填充掉，然后把左右两边分成两部分，所以很明显：

      

      又因为它的n是500，所以高精度即可。

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> using namespace std; int n; struct node{ int l,d[10010]; node operator*(int a)const{ node q; for(int i=1;i<=l;i++) q.d[i]=d[i]*a; q.l=l; for(int i=1;i<=q.l;i++) if(q.d[i]>9){ if(i==q.l) q.l++,q.d[i+1]=0; q.d[i+1]+=q.d[i]/10; q.d[i]%=10; } return q; }1 node operator/(int a)const{ node q; int tot=0; for(int i=l;i>=1;i--){ tot=tot*10+d[i]; q.d[i]=tot/a; tot%=a; } q.l=l; while(q.d[q.l]==0 && q.l>1) q.l--; return q; } }h[510]; int main(){ scanf("%d",&n); h[0].l=h[1].l=1; h[0].d[1]=h[1].d[1]=1; for(int i=2;i<=n;i++) h[i]=h[i-1]*(4*i-2)/(i+1); for(int i=h[n].l;i>=1;i--) printf("%d",h[n].d[i]); }