HDU 2062 子集序列：組合數學與字典序第 m 個排列子集構造

題目大意

集合 {1,2,...,n} 的所有非空子集，按「先按大小遞增，同大小按字典序」排序。求第 m 個子集的元素列表。
例 n=2：{1}, {1,2}, {2}, {2,1}。

核心洞察

• 固定首元素 k，剩餘 n-1 個元素可組成的排列子集總數為 sum[n-1]（預計算）。
• 第 m 個子集的首元素索引 t = (m-1) / sum[n-1] + 1（1-based）。
• 遞推處理剩餘位置，直到 m 歸零。

預計算組合數

A[i][j] = 從 i 個元素中取 j 個排列的數量 = A[i-1][j-1]*j + A[i-1][j]
sum[i]  = Σ A[i][j] (j=1..i)  // i 個元素的所有非空排列子集總數

構造算法（迭代版）

int num[21];  // 剩餘可用元素，初始 1..n
int len = n;
while (m > 0) {
    int t = (m - 1) / sum[len-1] + 1;  // 當前位選第 t 小的可用元素
    output num[t];
    m -= (t - 1) * sum[len-1] + 1;     // 跳過前面的塊
    // 從 num 中移除已用元素
    for (int k = t; k < len; ++k) num[k] = num[k+1];
    --len;
}

完整代碼（含多測試用例讀入）

#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 21;
LL A[MAXN][MAXN], sum[MAXN];

void init() {
    for (int i=0;i