题解 [AGC035C] Skolem XOR Tree

止步于一个死胡同里了,没能换一种思路出正解。感觉做这种构造题的方向也没有搞对。

构造一颗大小为 2n2n 的树,iii+ni+n 的权值都是 ii, 使 ii2i2i 路径上的异或和都为 ii 或断言这不可能。

开始的时候去研究了一下连续数异或的性质,发现连续四个一组异或起来是 00,如下。

00000
00001
00010
00011
---
00100
00101
00110
00111
---
01000
01001
01010
01011
---
01100
01101
01110
01111

这一点的正确性挺显然的,于是我们对于 n=4k+3n = 4k+3 的就有了一种构造方案,即把三个一组,后面每四个一组进行构造,用笔模拟一下发现四个四个的构造都是独立且成立的,那么随便选一个点连起来就可以了。

那么其它情况呢?能断言其不成立吗?我就束手无策了。

其实一条路走不通,得确定它确实走不通,然后换条路试试,而不可放弃啊。

其实做这种构造题应该先确定一个绝对没有解的条件,再去尝试构造剩下的。

那么什么事绝对没有解的呢?nn22 的幂次的时候肯定不行,因为 nnnn' 中间在这最高位上肯定不会有了。

那么考虑剩下的怎么去构造,其实有一个很“显然”的性质,那就是 xx 是偶数时,x+11=x+1x+1 \oplus 1 = x+1, 是奇数时,x1=x1x \oplus 1 = x-1, 那么我们就可以用下图构造了。

把每一组偶数 xx 都向上面连接就可以了。

至于 11, 直接接在 22 下面就好了,23=12 \oplus 3 = 1。还有就是 nn 是偶数时会多出来,再想想怎么修补。

可发现 nlowbit(n)1nlowbit(n)+1nn \rightarrow \text{lowbit}(n) \rightarrow 1 \rightarrow n - \text{lowbit}(n)+1 \rightarrow n' 满足条件,而 lowbit(n)\text{lowbit}(n) 是偶的,所以这样的路一定存在。

代码就不放了。