[AGC035C] Skolem XOR Tree 题解

_bestow · 2021-08-03 21:13:18 · 题解

AGC 就应该出这种有趣构造题。

首先考虑 n=2^k 的情况，显然 n\to 2n 的路径无法满足情况，所以无解。

我们想要一条路径异或起来等于某个值 x，那么考虑异或的性质，我们不妨找到一个 x\bigoplus k，和 k，然后把他们两个异或起来。还可以发现这个 k 直接取 1 就可以。所以对于每个 x,x\bigoplus 1 我们都可以把它们和 1 串起来，最后 1 再随便串一个即可。

但是这样如果 n 是偶数时没有 n\bigoplus 1，我们这时考虑再串一个 y，我们发现取 y=n-1 时刚刚好，由于 n 是偶数，那么 n\bigoplus n-1 一定全是 1 且不止一个 1 的二进制数。再异或一个 1，必然可以找到。我们把它们串起来，就可以得到答案。

代码非常简单，就不放了。