浣熊的小游戏题解

官方题解已经过审：https://www.luogu.com.cn/article/8rkkw6gb。

申明：本题解作者为本题出题人【数据删除】，因不能挂名，已经过原作者同意，由我代发。

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

简要证明如下：

首先，我们选择很多对相邻两个数异或，得到的一定是偶数个数异或的结果，因为每次新加进来了一对相邻数的异或，这对数里若有

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≤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

CPP

#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";
}
}

浣熊的小游戏题解

文章操作

CODE

相关推荐

评论

浣熊的小游戏题解