WZK打雪仗 jzoj 1997 题目大意：
在一个环上有n*2个点，问有多少种连法可以用n条线连接成n对点
输入样例 5 输出样例 42 解释：
一种可行的方案如下：
数据范围
对于30%数据： n<=30。
对于100%数据： n<=100。
解题思路：
这题其实很像，把一个图分割成多块的分割法，我们每一次分割后，看放在两边的点分别有多少对，这就很像Catalan数，我们设 f [ i ] f[i] f[i]为 i i i个点的分割法的种数，然后可以推出一下方程：
{ f [ 0 ] = 1 f [ 1 ] = 1 f [ i ] = ∑ j = 0 i ? 1 f [ j ] ? f [ i ? 1 ? j ] \left\{\begin{matrix}f[0]=1\\ f[1]=1\\ f[i]=\sum_{j=0}^{i-1}f[j]*f[i-1-j]\end{matrix}\right. ????f[0]=1f[1]=1f[i]=∑j=0i?1?f[j]?f[i?1?j]?
其次是因为答案很大所以要高精
代码： #include<cstdio>using namespace std;typedef long long ll;ll n,k,s[15],f[150][15];void gjc(ll x,ll y)//高精乘{for (int i=1;i<=10;++i) for (int j=1;j<=10;++j) { s[i+j-1]+=f[x][i]*f[y][j]; s[i+j]+=s[i+j-1]/1000000000; s[i+j-1]vps云服务器%=1000000000;}}void gjj(ll x)//高精加{for (int i=1;i<=10;++i) { f[x][i]+=s[i]; f[x][i+1]+=f[x][i]/1000000000; f[x][i]%=1000000000; s[i]=0; }}int main(){scanf(“%lld”,&n);f[0][1]=1;f[1][1]=1;for (int i=2;i<=n;++i) for (int j=0;j<i;++j)//DP { gjc(j,i-j-1); gjj(i);}int k=10;while(!f[n][k]&&k>0) –k;//压位高精输出printf(“%lld”,f[n][k]);for (int i=k-1;i>0;–i) printf(“%0*lld”,9,f[n][i]);return 0;}
