[AGC035C] Skolem XOR Tree 题解

· · 题解

首先发现 n=2^k 时最高为位只有 n 有 1，显然无法构造一条首尾都为 n 的链的异或值为 n。

考虑符合条件的树长什么样子：对于 x，x 和 x+n 路径上的所有点的异或值为 x，比如 2\to4\to6\to2+n\to4+n\to6+n 这样一条链。

也就是说如果我们现在有 x_1\oplus x_2\oplus x_3\cdots\oplus x_m=0，我们就可以把这些点依次串起来得到一条链。或者如果有 x_1\oplus x_2\oplus x_3\cdots\oplus x_m=X，我们可以构造一条 x_1\to x_2\to x_3\to\cdots\to x_m\to X\to x_1+n\to\cdots\to x_m+n 的链（前提是 X 已经被另外安排好了位置）。后面将这两种链分别简记为 x_1\to x_2\to x_3\to\cdots\to x_m 和 x_1\to x_2\to x_3\to\cdots\to x_m\leadsto X。

然后我们发现如果 n 是一个奇数，那么 \bigoplus\limits_{i=1}^{n}i\in\{0,1\}。也就是说要么可以一条链拉完，要么就先放 1\to2\to3，再用 1 连接剩下的链。

然后我们发现如果 x 是一个偶数就没有如此优秀的性质了。

考虑记 \bigoplus\limits_{i=1}^{n}i=z。记 x 表示 z 除去 2^0 位后的最低位的 1 对应值。因为一开始就判掉 n=2^k 了，所以显然是能取到值的。考虑先放一条 2\to x\to x+2 或者当 x=2 时放一条 4\to2\to6。将这 3 个数记为 a,b,c。

然后记 y=z\oplus x,u=y\oplus 1，然后放一条 x+1\to y\to u\leadsto x 的链。

最后记剩下的 n-6 个数为 x_{1,n-6}，放一条 x_1\to x_2\to x_3\to\cdots\to x_{n-6}\leadsto y 的链就完了。

考虑证明这样的正确性：

首先考虑 3 条链的合法性：我们第一步放置的 a\to b\to c，显然是满足 a\oplus b\oplus c=0 的；第二步的 y\oplus u=1,(x+1)\oplus 1=x 所以有 (x+1)\oplus y\oplus u=x；剩下的 \bigoplus\limits_{i=1}^{n-6}x_i=z\oplus(a\oplus b\oplus c)\oplus((x+1)\oplus y\oplus u)=z\oplus x=y。

再考虑证明 a,b,c,x+1,y,u 互不相同且均不超过 n：首先，显然 a,b,c,x+1 互不相同以及 y\neq u。因为 x+1=x\oplus 1,x\oplus y=z,z\neq 0,z\neq 1,y\oplus u=1，如果有相等可以简单地推出矛盾。

但是我们发现好像上述证明只对 n>6 有用，所以 n=6 手玩一下特判就可以了。

代码。