题解：CF2160C Reverse XOR
S1lver_W0lf
·
·
题解
题解：CF2160C Reverse XOR
题目分析
题意易懂，这里不再赘述。
以下对于字符串的描述，下标均以 1 开始。
简单分析一下：
对于由数字 x 转换而来的 01 串 S_x，第 i 位的数字翻转后将会对应到第 |S_x| - i + 1 位，其中 |S| 指字符串 S 的长度。相反地，第 |S_x| - i + 1 位的数字在翻转后将会对应到第 i 位。
由此我们可以得出结论：对于由数字 n 转换而来的 01 串 S_n，第 j 位的值必须要和第 S_n - j + 1 位相等（也就是说， S_n 是一个回文串），否则 x \oplus f(x) = n 不成立。
由异或的性质可得，如果异或值为 0，那么这一位上的两个数相等。不难发现，对于 S_n 的每一个后缀零，我们在 S_n 的前方添加前导零，是不会影响正确性的判断的。
这一部分可能有点难懂，举个例子：对于 3，它的二进制表示是这样的：11。不难发现，当 x = 2 时，有 2 \oplus f(2) = 3。随后，我们在 11 前后各添加一个 0，变为 0110，即十进制数 6。可以发现，只需要在 2 的二进制表示 10 前后各添加一个相同的数，异或串的前后就会各多出一个 0，满足我们之前在串前后增加的 0。
最后，如果补充完前导零后的 |S_n| 为一个奇数，那么第 \dfrac{|S_n| + 1}{2} 位（即中间位）应当为 0。因为此时，翻转前和翻转后的第 \dfrac{|S_n| + 1}{2} 位的值一定相等，所以异或值一定为 0。