# include <stdio.h>
# include <stdbool.h>
long long refer[21][21][2];

void start()
{
    memset(refer,0,sizeof(refer));
    refer[2][1][1]=1;
    refer[1][1][0]=1;
    refer[2][1][0]=0;
    refer[2][2][1]=0;
    refer[2][2][0]=1;
    int i,j,k;
    for(i=3;i<=20;i++)
    {
       for(j=1;j<=i;j++)
       {
        long long t2=0;
        for(k=j;k<=i-1;k++) t2+=refer[i-1][k][0];
        refer[i][j][1]=t2;
        t2=0;
        for(k=1;k<j;k++) t2+=refer[i-1][k][1];
        refer[i][j][0]=t2;
       }
    }
}
int cul(int num,bool data[])
{
 int i=0,j=1;
 for(j=1;;j++)
 {
  if(!data[j])
  {
   i++;
  }
  if(i==num)
  {
     data[j]=1;
     return j;
  }
 }
}
int main()
{

    start();

    
    int test,i;
    scanf("%d",&test);
    for(i=1;i<=test;i++)
    {
      int num,j,k;
      long long pos; 
      scanf("%d %I64d",&num,&pos);
      if(num==1) 
      {
        printf("1\n");
        continue;
      }

      int res[21];
      long long total=0;
      int last;
      int chk;
      for(j=1;j<=num;j++)
      {
       if(total<pos)
       {
        last=j;
        chk=0;
        total+=refer[num][j][0];
       }
       else break;
       if(total<pos)
       {
        last=j;
        chk=1;
        total+=refer[num][j][1];
       }
       else break;
      }
      total-=refer[num][last][chk];
      pos-=total;
      res[1]=last;
      for(j=num-1;j>=1;j--)
      {
       total=0;
       if(chk)
       {
        chk=0;
        for(k=last;k<=j;k++)
        {
         if(total<pos)
         {
          last=k;
          total+=refer[j][k][chk];
         }
         else break;
        }
       }
       else
       {
        chk=1;
        int tlast=last;
        last=1;
        for(k=1;k<tlast;k++)
        {
         if(total<pos)
         {
          last=k;
          total+=refer[j][k][chk];
         }
         else break;
        }
       }
       res[num-j+1]=last;
       if(total!=0) total-=refer[j][last][chk];
       pos-=total;
     }

     bool final[21];
     memset(final,0,sizeof(final));
     for(j=1;j<=num;j++) printf("%d ",cul(res[j],final));
      printf("\n");
    }
         
  
   
}
                               

• 多谢，思维不严谨啊 (0) 090609103 2011-12-06 20:46:44