AT_agc035_c [AGC035C] Skolem XOR Tree

感觉每次遇到这种神秘构造都会跪下。

首先如果 \(n\) 为 \(2\) 的正整数次幂，由于第 \(n\) 位为 \(1\) 的只有一个数，显然会跪下。

然后我们通过构造证明除了这种情况都是有解的，分奇数和偶数考虑。

你考虑到一个性质，当 \(i\)为偶数的时候，有 \(i \text{xor} 1 = i + 1\)，我们将每个这种 \(i\) 与 \(i + 1\) 分别连边，具体来说：

• \(1 \to i, 1 \to i + 1 + n, i \to i + 1, i + n \to i + 1 + n\)。

对于 \(1\)，和 \(n + 1\) 随便找个匹配即可，如果是偶数，那么剩下一对数找到 \(n - lowbit ( n)\) 时的点，很容易连上边。