CF1787E The Harmonization of XOR 题解

题面

将集合 \(\left\{1, 2, \cdots, n\right\}\) 划分为 \(k\) 个非空不交子集，使得每个子集的异或和均为 \(x\)。

（\(1 \le n,k \le 2 \times 10^5\)）。

题解

首先显而易见的判断一下无解的情况，记 \(sum = \bigoplus\limits_{i = 1}^{n} i\)，如果 \(k\) 为奇数但 \(sum \neq x\) 或者 \(k\) 为偶数但 \(sum \neq 0\) 都一定无解，下文假定已经判断出这种情况。

可以发现任意三个满足要求的子集可以合并为满足要求的一个大集合，所以任务转化为最大化合法子集的数量。可以发现 \(\left\{a, a\oplus x\right\}\) 和 \(\left\{x\right\}\) 这两种集合显然是满足要求的，所以优先构造这两种集合，剩下的元素最后合并到这些集合中。

下面对这种构造方式最优进行证明，该种构造方式最优，当且仅当剩下的元素构成的集合 \(S\) 不能分裂成多个满足要求的集合。

设 \(x\) 在二进制表示下的最高位为 \(B\)，如果 \(S\) 可以分裂成多个满足要求的集合，那么 \(S\) 中一定存在二进制下第 \(B\) 位为 \(1\) 的数，假定其为 \(p\)。因为 \(B\) 为 \(x\) 二进制表示下的最高位，所以 \(x\) 二进制下第 \(B\) 位一定为 \(1\)。进而可以得出 \(x \oplus p < p\)，考虑 \(m = x \oplus p\) 是否会在其他集合构造时被使用，首先第一种集合 \(\left\{a, a\oplus x\right\}\)，显然如果 \(m\) 在该集合中，那集合的另一个元素一定为 \(p\)，与 \(p\) 未使用矛盾；考虑第二种情况 \(\left\{x\right\}\)，因为 \(p > 0 \Rightarrow m \neq x\)，矛盾。

因此在这种构造方式下，剩下的元素构成的集合 \(S\) 的异或和不可能为 \(x\)，又考虑到最开始判出了总异或和不合法的情况，所以集合 \(S\) 的异或和一定为 \(0\)，所以在最终求解时直接将 \(S\) 并入任意一个先前构造出的合法集合中。

Code

//Codeforces - 1787E
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

int main() {
    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N, K, X;

        std::cin >> N >> K >> X;

        valueType xorSum = 0;

        for (valueType i = 1; i <= N; ++i)
            xorSum ^= i;

        if (((K & 1) == 1 && xorSum != X) || ((K & 1) == 0 && xorSum != 0)) {
            std::cout << "NO" << '\n';

            continue;
        }

        ValueVector remain;
        ValueMatrix ans;

        for (valueType i = 1; i <= N; ++i) {
            if (i == X) {
                ans.emplace_back(1, i);
            } else if ((i ^ X) > N) {
                remain.emplace_back(i);
            } else if ((i ^ X) < i) {
                ans.push_back({i, i ^ X});
            }
        }

        if (ans.size() < K) {
            std::cout << "NO" << '\n';

            continue;
        }

        for (valueType i = K; i < ans.size(); ++i)
            ans[0].insert(ans[0].end(), ans[i].begin(), ans[i].end());

        ans[0].insert(ans[0].end(), remain.begin(), remain.end());

        std::cout << "YES" << '\n';

        for (valueType i = 0; i < K; ++i) {
            std::cout << ans[i].size() << ' ';

            for (auto const &value: ans[i])
                std::cout << value << ' ';

            std::cout << '\n';
        }
    }
}