Trees Made to Order

We can number binary trees using the following scheme: 
The empty tree is numbered 0.
The single-node tree is numbered 1.
All binary trees having m nodes have numbers less than all those having m+1 nodes.
Any binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered > n have either
Left subtrees numbered higher than L, or
A left subtree = L and a right subtree numbered higher than R.

The first 10 binary trees and tree number 20 in this sequence are shown below:



Your job for this problem is to output a binary tree when given its order number.

1
20
31117532
0

X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)

题目的意思是有很多二叉树排成一列，在左边的二叉数的节点数小于右边的二叉树，如果节点数相同那么先比较根结点的左子树上的节点数，以此类推，就能得到一串二叉树序列。现在给你一个数n，你的任务是找到编号为n的二叉树并把它按题目所要求的格式输出~~~~1<=n<=500，000，000

    庆哥曾经曰过：少年，不要做太难的题。。。    可是我觉得acm吸引我的只有那些难题，这些题比那些坑爹般的物理竞赛题有意思多了~

ac一道题的感觉其实比dota抢了一个人头的感觉还好的~呵呵

这是一道难度为3级的组合数学题，开始想的时候觉得这题挺复杂的，尤其是在敲的时候，一些细节方面其实是很复杂的，不过大体思路还是简单的~~嘿嘿

#include<iostream>
using namespace std;
const int maxn=22;
__int64 n,hi,nx;
__int64 a[maxn]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190};

//这就是传说中kd的卡特兰数，tm的直接打表不解释！
__int64 b[maxn];
__int64 c[maxn][maxn];
struct pp
{
    __int64 x;
    int i;
}pos;   
int find(__int64 x)
{
    for(int i=0;i<maxn;i++)
    {
        if(x<=b[i])
        {
            return i;
        }
    }
}   
pp find2(__int64 x,int y)
{
    for(int i=0;i<=y-1;i++)
    {
        x-=c[i][y-1-i];
        if(x<=0)
        {
            x+=c[i][y-i-1];
            pos.x=x-1;
            pos.i=i;
            return pos;
        }
    }
}            
void fuck(int h,__int64 x)
{
    
    if(h==0)
    {
        return ;
    } 
    pp tx = find2(x,h);
    if(tx.i!=0)
    {
        printf("(");
        fuck( tx.i, (tx.x/a[h-tx.i-1] ) + 1);
        printf(")");
    }
    printf("X");
    if(h-tx.i-1!=0)
    {
        printf("(");
        fuck( h-tx.i-1, (tx.x%a[h-tx.i-1]) + 1 );
        printf(")");
    }
    return ;
}
int main()
{
    b[0]=0;
    for(int i=1;i<maxn;i++)
    {
        b[i]=b[i-1]+a[i];
    } 
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<maxn;j++)
        {
            c[i][j]=a[i]*a[j];
        }
    }
    while(scanf("%I64d",&n))
    {
        if(n==0)
        {
            break;
        }
        hi=find(n);
        nx=n-b[hi-1]; 
        fuck(hi,nx);   
        printf("n");
    }
    return 0;
}

Time：0ms    Memory：236k   Date：2011/8/21