#include <iostream>

using namespace std;

#define SIZE 20
#define a(length,x) a[length][x]       //a(i,j)表示长为length,以x开头的前两个数呈上升的篱笆的个数 
#define b(length,x) a[length][length-x+1] //b与a类似，前两个数呈下降。b矩阵每行是a矩阵每行的逆置 


enum Direction{UP=0,DOWN};

__int64 a[SIZE+1][SIZE+1];

void init()
{
	a(1,1)=1;

    int row,col;
	for(row=2;row<=SIZE;row++)
	{
		for(col=row-1;col>=1;col--)
		{
			a(row,col)=a(row,col+1)+b(row-1,col);
		}	
	}
}

void searchNext(int length,__int64 order,int bound,Direction dict,int *m)
{
    if(length==1)
    {
        int i=1;
        while(m[i])
            i++;
        m[i]=1;
        cout<<i<<" ";
        return;
    } 
    
    if(dict==UP)
    {
        int i=0;
        do
        {
            i++;
            order-=a(length,i);
        }while(order>0);
        order+=a(length,i);
        
        int k=0;
        for(int j=0;j<i;j++)
        {            
            while(m[++k]);
        }
        m[k]=1;
        cout<<k<<" ";        
        
        searchNext(length-1,order,i,DOWN,m);
    }
    else
    {  
        int i=bound-1;
        do
        {
            i++;
            order-=b(length,i);
        }while(order>0);
        order+=b(length,i);
       
        int k=0;
        for(int j=0;j<i;j++)
        {            
            while(m[++k]);
        }
        m[k]=1;
        cout<<k<<" ";        
        
        searchNext(length-1,order,i,UP,m);
    }
}

void search(int length,__int64 order)
{	
    //找第一个篱笆  
    
    if(length==1)
    {
         cout<<1;
         return;
    }
    
    int m[21];
    for(int i=1;i<=length;i++)
        m[i]=0;
        
    int first=0;
    do
    {
        first++;
        order=order-b(length,first)-a(length,first);
    }while(order>0);
    m[first]=1;
    cout<<first<<" ";
    
    //递归找下一个篱笆 
    Direction dict;
    order=order+b(length,first)+a(length,first);
    if(order-b(length,first)<=0)
    {
        dict=UP;
    }
    else
    {
        order=order-b(length,first);
        dict=DOWN;
    }
    
    searchNext(length-1,order,first,dict,m);
}

int main()
{
	init();			//初始化矩阵	

	int testCases;			
	cin>>testCases;

	while(testCases--)
	{
		int length;		
		__int64 order;		
		cin>>length>>order;

		search(length,order);
		
		cout<<endl;
	}
	
	return 0;
}

• Re:终于PASS了... (61) tzkq 2009-09-26 15:55:13