NC275631 嘤嘤不想求异或
讲真牛客这次的直播录屏讲得挺烂的（暴论），板书烂，表达烂...
求 \(1\sim x\) 的异或和
当然，求异或和本质上是求每一位的二进制值。
前置知识：
- 和十进制一样，二进制下最左边是高位，最右边是低位；
- 异或和计算中，偶数个 \(1\) 结果为，反之为 1。
循环周期推导
接下来推导为什么异或和的循环周期为 \(4\)：
先从最基本的 \(1\;xor\;2\;xor\;3\;xor\;4 = 0\) 开始，
001 (1)
010 (2)
011 (3)
100 (4)
注意到前两位的 \(1\) 都是偶数，在排列组合中，两位的全排列需要 \(A_2^2=4\) 次完成，在这个周期内后面两位的异或结果为 \(0\)，对后续周期没有影响。
再往下一个周期：
0100
0101 (1)
0110 (2)
0111 (3)
1000 (4)
将上个周期附加在下个周期的开头，由于前两位都是 \(0\)，所以对异或结果没有影响。
也就是说，在 \(T=4\) 的情况下，每 4 次前 \(n-1\) 位的 1 的个数为偶数，则此时异或和等于该周期的最后一个数，即：
\[(x-3)\;xor\;(x-2)\;xor\;(x-1)\;xor\;x= x
\]
由右端点推出异或和
根据上面的规律，可以继续推导最后一个周期中的四个数与最终异或和的关系：
- 显然结果为 1
- \(x+1\)，第一位结果为 1，等价于当前数再加 1
- \(0\)，此时各位 \(1\) 都是偶数个
- 在 (3) 的情况下多写了一位，最终异或和就是当前数本身。
求 \(l\sim r\) 的异或和
已经知道异或和的值反映的是当前位上 \(1\) 的奇偶个数，又知道以下规律：
- 奇+奇=偶
- 奇+偶=奇
- 偶+偶=偶
也就是 \([1,l-1]_1+[l,r]_1=[1,r]_1\)，根据已知规律可求的 \([1,l-1],[1,r]\) 即可唯一对应到 \([l,r]\) 的奇偶数，进而求出该位的异或和值。
不难发现，令奇数为 \(1\)，偶数为 \(0\)，\([l,r]_1=[1,l-1]_1\;xor\;[1,r]_1\)。