P17796 [CXOI R7-A] 追忆岁月 题解

Official Solution.

因为 $n$ 个数最多有 $2^n$ 种选取方法，而需要覆盖的数的数量也是 $2^n$，这就告诉我们构造的序列 $a,b$ 需要满足所有的子集的异或均两两不同。

最小值

构造 $a_i=2^{i-1}$ 即可。很显然不能得到和更小的序列。

最大值

构造序列 $a_1=2^n-1,a_i=2^n-2^{i-2}-1(i\ge 2)$，然后翻转整个序列即可。

下面证明一下这个为什么一定取到了最大值：首先如果存在一个 $a_i$ 满足二进制第 $n$ 位为 $0$ 的话，那么就算其他数全取最大值是合法的，其和也无法比现在构造的序列的和要大。

而若存在两个二进制位，其在每个 $a_i$ 内的值都相同，那么对于每个选出的 $a$ 的子集得到的异或值，这两个二进制位都必然相同，也就必然无法表示出所有的数。因此任意两个二进制位，都至少存在一个位置 $i$ 使得 $a_i$ 在这两个二进制位上得到的值不同。因此其余二进制位必然不能全都是 $1$。

而因为剩下 $n-1$ 个二进制位和 $n-1$ 个 $a_i$ 的值没确定，所以考虑对剩下的每个二进制位都选择一个不同的 $a_i$，把其相应的二进制位值设为 $0$。一个可行的方案就是 $i\ge 2$ 都有 $a_i=2^n-2^{i-2}-1$，然后将 $a$ 序列从小到大排序即可。因为这样构造得到的 $a$ 序列是单调递减的，所以可以直接翻转。

总时间复杂度为 $O(Tn)$。

:::success[代码实现]

namespace Loyalty
{
    int a[N];
    inline void init() {}
    inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int _atc)
    {
        int n;
        cin >> n;
        cout << 1 << '\n';
        for (int i = 1; i <= n; ++i)
            cout << (1ll << (i - 1)) << ' ';
        cout << '\n';
        a[1] = (1ll << n) - 1;
        for (int i = 2; i <= n; ++i)
            a[i] = (1ll << n) - 1 - (1ll << (i - 2));
        for (int i = n; i; --i)
            cout << a[i] << ' ';
        cout << '\n';
    }
} // namespace Loyalty

:::

当然你也可以直接写个线性基上去直接算出来序列的下一个元素，当然这就没什么必要了（）