# HDU 2062 Subset sequence

```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```

n=3的情况

f(n)代表集合An所有子集的个数，那么有递推关系：

f(n) = n * (f(n - 1) + 1)， f(1) = 1

``` 1 //#define LOCAL
2 #include <iostream>
3 #include <cstdio>
4 #include <cstring>
5 using namespace std;
6
7 int main(void)
8 {
9     #ifdef LOCAL
10         freopen("2062in.txt", "r", stdin);
11     #endif
12
13     int n;
14     bool taken[25];
15     int b[25];
16     long long m, a[25];
17     a[1] = 1;
18     for(int i = 2; i <= 20; ++i)
19         a[i] = i * (a[i - 1] + 1);
20
21     while(scanf("%d%I64d", &n, &m) == 2)
22     {
23         memset(taken, false, sizeof(taken));
24         int i;
25         long long r = 1;
26         for(i = 1; i <= n; ++i)
27         {
28             b[i] = ((m - 1) / (a[n - i] + 1)) + 1;
29             int j, k = 0;
30             for(j = 1; j <= n; ++j)
31             {
32                 if(!taken[j])
33                     ++k;
34                 if(k == b[i])
35                     break;
36             }
37             b[i] = j;
38             taken[j] = true;
39             r = (m - 1) % (a[n - i] + 1);
40             if(r == 0)
41                 break;
42             m = r;
43         }
44         for(int j = 1; j < i; ++j)
45             printf("%d ", b[j]);
46         printf("%d\n", b[i]);
47     }
48     return 0;
49 }```

HDU 2062 Subset sequence,布布扣,bubuko.com

## HDU 2062 Subset sequence 数位dp,思路 难度:1

http://acm.hdu.edu.cn/showproblem.php?pid=2062 Subset sequence Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3569    Accepted Submission(s): 1802 Problem Description Consider the aggregate An=

## hdu 2062 Subset sequence【有点康拓展开的意思】

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,

## 2062 Subset sequence

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.