题解：P15235 浣熊的小游戏

· · 题解

这个 idea 是三年前想到的，当时我还不知道什么是线性基。

Solution

我们使用人类智慧将题意进行转换，发现原题等价于使用值域内相邻两数的异或和能异或出多少种值。

简要证明如下：

首先，我们选择很多对相邻两个数异或，得到的一定是偶数个数异或的结果，因为每次新加进来了一对相邻数的异或，这对数里若有 1 个之前已经被加进来，因为 a ⊕ a=0，相当于被取出去了，取一加一，数的数量的奇偶性不变，两个都没加进来与两个都加进来了情况类似。

然后，所有偶数个数异或，都一定可以通过相邻两数异或出来。我们将这偶数个数从左至右两两配对，对于每一对数 i,j(i<j)，我们把 i,j 中间的数异或两遍，结果不变，同时使用结合律，可知 i⊕j=(i⊕i+1)⊕(i+1⊕i+2)⊕...⊕(j-1⊕j)，其中每一项都是相邻两数的异或值，再把每一对 i,j 异或起来，得到的就是这偶数个数异或的结果。

可这有什么用呢？我们会发现相邻两数异或起来得到的值十分特殊，容易发现在二进制下对一个数加 1，实际上就是把该数从低位到高位的第一个 0 变成 1，再把后面所有的 1 变成 0，前面的位不变，于是这两个数异或起来就是一堆 1。

又因为 r\leq 10^{18}，实际上相邻两数异或值至多有 60 种。

再考虑这些数异或起来有多少种结果，当然你可以写线性基，直觉一下不难发现其结果就是 2^n-1（n 为相邻两数异或值种类数），原因可以理解为每一种异或值相当于一个灯泡，n 个灯泡就有 2^n 种开关方式，再减去全关的即为 2^n-1。

做到这里可以拿 50 分。

接下来，考虑快速找到范围内相邻两数异或值种类数。容易发现如果存在相邻两数异或值为 m 个 1，在二进制下，异或成这两个值的那两个数中较大的数从低到高第 m 位一定为 1，该 1 后面则全是 0，也就是说，这个数一定是 2^{m-1} 的倍数，且不是 2^m 的倍数。

我们枚举 m，判断该区间去掉 l 后是否存在这样的数即可。

注意到该判断与求一个区间内 2^m 的倍数个数是否等于 2^{m-1} 的倍数个数是等价的，这样我们就可以 O(1) 判断了。

总的时间复杂度 O(q\log r)，具体实现非常简洁，甚至代码比T1短。

PS：注意到 2^m 倍数不等于 2^{m-1} 倍数的是一段前缀加一个点，且前缀长度大致为 \log_2(r-l)，因此直接取对数向上调整即可做到 O(q)，但由于取 \log 时间太慢而位运算速度太快，二者效率差别不超过 0.1s，也就没有卡 \log 做法了。

CODE

#include<bits/stdc++.h>
using namespace std;
long long q,l,r,ans,i;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>q;
while(q--){
cin>>l>>r;
ans=0;
for(i=0;i<=60;i++)
if(((r>>i)-(l>>i))!=((r>>i+1)-(l>>i+1)))
ans++;
cout<<(((long long)1<<ans)-1)<<"\n";
}
}