题目链接：https://atcoder.jp/contests/abc121/tasks/abc121_d
题目很裸（Atcoder好像都比较裸
就给一个区间求异或和
n到1e12
肯定不能O(n)推
那肯定得通过异或的一些性质
用$f\left( a,b\right)$表示[a,b]区间的异或和
我只观察出了$f\left( 2^{a},2^{b}-1\right)$的异或和肯定为0。
通过$f\left( 2^{a},2^{a+1}-1\right)$每一位都会出现偶数次
例如 [4,8)
4 ： 100
5 ： 101
6 ： 110
7 ： 111
异或和就为0
那么的$f\left( 2^{a},2^{b}-1\right)$ = $f\left( 2^{a},2^{a+1}-1\right)$ ^ $f\left( 2^{a+1},2^{a+2}-1\right)$ ^ ... ^ $f\left( 2^{b-1},2^{b}-1\right)$ = 0
在这里参考了大佬的博客https://www.cnblogs.com/Mychael/p/8633365.html原来有结论orz
得到上述结论后 不难得到 $f\left( 0, n\right)$ = $f\left( 2^{k}, n\right)$
分奇偶来看
当n为奇数
那么$f\left( 2^{k}, n\right)$ k的那一位会出现 n - 2^{k} + 1次 也就是偶数次
那么最后结果最高位就为0了 $f\left( 2^{k}, n\right) = f\left( 0, n-2^{k}\right)$ 不清楚可以看下上面 4，5，6，7的例子
是不是最高位的1都可以减去了 也就是都减去4 $f\left( 4, 6\right) = f\left( 4 - 4, 6 - 4\right) = f\left( 0, 2\right)$ 没错吧！
$f\left( 0, n-2^{k}\right)$ 又可以表示为 $f\left( 0, n'\right) = f\left( 2^{k-1}, n'\right)$ 接着推推推
推到最后 到了0~4的范围里 为啥到4(2的2次)而不是到2(2的1次)呢
因为上述结论是 $f\left( 2^{a},2^{a+1}-1\right) = 0$ 如果a等于0了 $f\left( 2^{0},2^{1}-1\right) = f\left( 1,1\right) = 1 \neq 0$
所以结论只适用于a >= 1的情况 所以最后应该在0~4里面确定结论
$n\equiv 1\left( mod4\right)$ 那么最后还剩最末位一个1 即 $f\left( 0,n\right) =1$
$n\equiv 3\left( mod4\right)$ 那么最后还有1和3进行异或 最末位就为0了 即 $f\left( 0,n\right) =0$
n为偶数的时候（感觉原博主这部分的推导写错了 但结论是对的
假如这个n是2的次幂了 那么$f\left( 2^{a},n\right) = n$就ok了
如果不是的话 $f\left( 2^{k}, n\right)$ k的那一位会出现 n - 2^{k} + 1次 也就是奇数次 那么得保留
所以 $f\left( 2^{k}, n\right) = f\left( 0, n-2^{k}\right) Xor 2 ^{k}$ 这次得看$n-2^{k}$是否为2的次幂
是的话就是$f\left( 2^{k}, n\right) = f\left( 0, n-2^{k}\right) Xor 2 ^{k} = n-2^{k} Xor 2 ^{k} = n$
如果一直不是的话 就会把原来的n的每一位都积累起来 最后到$6 - 2^{2} = 2$ 这个时候最后还要异或上1 答案就是n+1
也就是 $n\equiv 0\left( mod4\right)$ $f\left( 0,n\right) =n$
$n\equiv 2\left( mod4\right)$ $f\left( 0,n\right) =n + 1$
总结成程序就是
int Xor(int a) {if (a % 4 == 0) return a;if (a % 4 == 1) return 1;if (a % 4 == 2) return a + 1;return 0; }
答案即为$f\left( a, b\right) = f\left( 0, b\right) Xor f\left( 0, a-1\right)$
代码如下
#include <cstdio> using namespace std;long long Xor(long long a) {if (a % 4 == 0) return a;if (a % 4 == 1) return 1;if (a % 4 == 2) return a + 1;return 0; }int main() {long long a, b;scanf("%lld%lld", &a, &b);printf("%lld", Xor(a -1) ^ Xor(b));return 0; }
推的过程比较混乱建议手动模拟一遍（￣▽￣）