http://poj.org/problem?id=1095
先求出n个节点数的二叉树的形态有多少种。卡特兰数f[n]=f[n-1]*(4*n-2)/(n+1);再递归求。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define maxn 200
using namespace std; ll f[maxn];
int n,m; void inti()
{
f[]=;
for(int i=; i<; i++)
{
f[i]=f[i-]*(*i-)/(i+);
}
} void deal(int n,int k)
{
int i,sum=;
if(n==) {printf("X"); return ;}
for(i=; sum+f[i]*f[n--i]<k; i++)
{
sum+=(f[i]*f[n--i]);
}
k-=sum;
if(i)
{
printf("(");
deal(i,(k-)/f[n--i]+);
printf(")");
}
printf("X");
if(i!=n-)
{
printf("(");
deal(n--i,(k-)%f[n--i]+);
printf(")");
} } int main()
{
inti();
while(scanf("%d",&n)!=EOF)
{
if(n==) break;
for(int i=; ; i++)
{
if(n>f[i])
{
n-=f[i];
}
else{
m=i;
break;
}
}
deal(m,n);
printf("\n");
}
return ;
}