详细题解

1. 问题本质

我们需要构造一个长度不超过 $200$ 的数组，使其恰好包含 $X$ 个递增子序列（包含空子序列）。注意题目中递增子序列计数包含重复位置产生的不同子序列，因此若数组中有重复元素，会指数级增加子序列数量。

例如，在一个严格递增的序列 $[1,2,3]$ 中，每个元素要么选要么不选，共有 $2^3 = 8$ 个子序列（包括空子序列）。若数组中包含相同元素，则选择其中某个特定元素会衍生更多分支。

2. 构造思想

标程采用递归构造，基于以下两条操作：

• 操作1（偶数 $X$）：如果 $X$ 为偶数，我们可以先构造一个含有 $X/2$ 个递增子序列的数组，然后在末尾添加一个比当前所有元素都大的数。
  新增的元素可以独立选择是否加入子序列，使得子序列总数翻倍：因为对于原数组的每一种子序列，新元素可以选或不选，且新元素必须放在末尾且递增性质仍保持（它是最大值）。因此新的总数 $= (X/2) \times 2 = X$。

• 操作2（奇数 $X$）：如果 $X$ 为奇数，我们可以先构造一个含有 $X-1$ 个递增子序列的数组，然后在末尾添加一个比当前所有元素都小的数。
  此时新元素只能单独构成一个长度为 $1$ 的新子序列（因为它是数组中的最小值，无法接在任何元素之后），所以子序列总数加 $1$，即 $(X-1) + 1 = X$。

• 基础情形：当 $X=2$ 时，最简单的数组是只包含一个元素，如 [0]。它的子序列有 $2$ 个：空子序列和 [0]。

3. 正确性分析

为什么这两种操作能覆盖所有 $X \ge 2$？

• 若 $X$ 为偶数，我们总是可以将其折半，最终归结到 $2$；
• 若 $X$ 为奇数，我们减 $1$ 后变为偶数，继续折半；
• 这类似于二进制表示的过程：从低位向高位构造，每次操作对应二进制位的 $0$ 或 $1$。事实上，最终数组的长度恰好等于 $\lceil \log_2 X \rceil$ 或略多，绝不会超过 $200$（因为 $X \le 10^{18}$，$\log_2 10^{18} \approx 60$，远远小于 $200$）。

注意：添加较小元素时，为了保证它是全局最小，我们取当前数组最小值减去 $1$；添加较大元素时，取最大值加 $1$。这样可以始终保持所有元素不同，并维持严格递增子序列的计数性质。

4. 实现细节

标程的 f(X) 函数返回一个 vector<int>，表示满足子序列数为 $X$ 的数组：

• 若 $X == 2$，返回 {0}。
• 若 $X$ 为奇数，先递归得到 $f(X-1)$，再 push_back 当前数组的最小值减 $1$。
• 若 $X$ 为偶数，先递归得到 $f(X/2)$，再 push_back 当前数组的最大值加 $1$。

由于递归深度约为 $O(\log X)$，时间空间均无压力。

5. 时间复杂度

每个测试用例递归 $\log X$ 层，每层求最小/最大值 $O(n)$，其中 $n \le \log X \le 60$。总复杂度 $O(t \log^2 X)$，完全可行。

6. 代码（附注释）

#include <bits/stdc++.h>
using namespace std;

// 返回一个数组，其递增子序列总数（含空）恰好为 x
vector<int> f(long long x) {
    vector<int> res;
    if (x == 2) {
        res.push_back(0);        // 基准情况：子序列数 = 2
    } else if (x & 1) {          // x 为奇数
        res = f(x - 1);
        int mn = *min_element(res.begin(), res.end());
        res.push_back(mn - 1);   // 添加更小的元素，子序列数 +1
    } else {                     // x 为偶数
        res = f(x / 2);
        int mx = *max_element(res.begin(), res.end());
        res.push_back(mx + 1);   // 添加更大的元素，子序列数翻倍
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        long long x;
        cin >> x;
        vector<int> ans = f(x);
        cout << ans.size() << '\n';
        for (size_t i = 0; i < ans.size(); ++i) {
            cout << ans[i] << " \n"[i + 1 == ans.size()];
        }
    }
    return 0;
}

7. 总结

本题通过巧妙的递归构造，利用添加“最大元素”使子序列数翻倍，添加“最小元素”使子序列数加一，将任意 $X$ 分解为一系列操作。由于 $X \le 10^{18}$，构造出的数组长度远小于 $200$，完美满足要求。该题展示了如何将组合计数问题转化为基于二进制表示的构造问题。