Subset sequence
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3441 Accepted Submission(s): 1740
Problem Description
Consider the aggregate An= { 1, 2, …, n }. For example, A1={1}, A3={1,2,3}. A subset sequence is defined as a array of a non-empty subset. Sort all the subset sequece of An in lexicography order. Your task is to find the m-th one.
Input
The input contains several test cases. Each test case consists of two numbers n and m ( 0< n<= 20, 0< m<= the total number of the subset sequence of An ).
Output
For each test case, you should output the m-th subset sequence of An in one line.
Sample Input
1 1 2 1 2 2 2 3 2 4 3 10
Sample Output
1 1 1 2 2 2 1 2 3 1
题意：给出n和m，然后有很多个集合{1,2，，，，n}的非空子集，按照一定方式排列，例如n==3时，
1
1
2
1
2
3
1
3
1
3
2
2
2
1
2
1
3
2
3
2
3
1
3
3
1
3
1
2
3
2
3
2
1
然后输出第m个序列。
结题思路，仔细观察可以看出，1、2、3开头的集合个数是一样多的，因此那m/(每组个数)可以得出第一个数字，然后依次类推即可
#include<cstdio>
#include<iostream>
#define LL long long int
using namespace std;
int main(){
int n,a[21],i;
LL m,t;
LL p[21]={0,1};
for(i=2;i<=20;i++){
p[i]=p[i-1]*(i-1)+1;//0、1、2、5、16
}
while(cin>>n>>m){
for(i=0;i<=20;i++)
a[i]=i;
while(n--&&m){
t=m/p[n+1]+((m%p[n+1])?1:0);
cout<<a[t];//当前的首数字
for(i=t;i<=n;i++)
a[i]=a[i+1];//回到n-1个数字，更新输出数组
m-=((t-1)*p[i]+1);//去掉前面的小于t开头的组合，且将去掉一个仅有t的集合
printf(m==0?"\n":" ");
}
}
return 0;
}
