Poj Solution 1037

http://poj.org/problem?id=1037

//* @author:
import java.util.*;
public class Main{
 static final int MAX=21;//���20��ľ��
 static long w[][];//w�����еĸ���
 static long m[][];//m�����еĸ���m[x][n]Ϊ��n��Ȳ�ͬ��ľ����ɵ�դ8�У������е�x��ľ��ʼ�ġ�M�������еĸ���
 
 private int n;//ľ��ĸ���
 private long c;//���

 private boolean flag[];
 private boolean print;
 
  static {//��ʼ����̬��
    w=new long[MAX][MAX];
    m=new long[MAX][MAX];
    w[1][1] = 1; m[1][1] = 1;
    w[1][2] = 0; m[1][2] = 1;
    w[2][2] = 1; m[2][2] = 0;
    for (int i = 3; i < MAX; i++)
      for (int j = 1; j < MAX; j++){
        for (int k = 1; k < j; k++) 
          w[j][i] += m[k][i - 1];
        for (int k = j; k < i; k++) 
          m[j][i] += w[k][i - 1];
    }
  }

  public Main(int n,long c){
    this.n=n;
    this.c=c;
    flag=new boolean[MAX];
    print=false;
   }

  private void fand(int k, int m){
    for (int i = 1; i <= m; i++) 
     if (flag[i] && i <= k){
        k++; m++;
     }
    flag[k] = true;
    if (print) System.out.print(" "+k);
    else{
        System.out.print(k);
        print = true;
    }
}

 private void doIt(){
   int k = 1;//��������ǰ���ľ������
        print = false;
        boolean direct = true, first = true;
        while(n!=0){
            if (direct)
                if (c > w[k][n]){//����Ŵ����Ե�k��ľ��ʼ�ġ�w�������еĸ���˵��������������Щ����֮��
                    c -= w[k++][n];//���±�ţ�ͬʱ��һ��ľ��
                    if (first) {direct = false; k--;}//����Dz��ҵ�һ��ľ���Ҫ��"m"������
                }else{
                    fand(k, n--);//�ҵ�k,����ľ�������1
                    first = false;
                    direct = false;
                    k = 1;
                }
            else
                if (c > m[k][n]){//����Ŵ����Ե�k��ľ��ʼ�ġ�m�������еĸ���˵��������������Щ����֮��
                    c -= m[k++][n];//���±�ţ�ͬʱ��һ��ľ��
                    if (first) direct = true;//���ҵ�һ��ľ�����
                }else{
                    fand(k, n--);
                    first = false;
                    direct = true;
                }
        }
        System.out.println();
    }

public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    int t, n;
     long c;
     t=sc.nextInt();;
    while((t--)!=0){
        n=sc.nextInt();
        c=sc.nextLong();
        Main m=new Main(n,c);
        m.doIt();
    }
}

 
}