0112模拟赛 吃干饭

0112模拟赛 吃干饭

题目大意:选择$[l,r]$中的若干数异或起来(也可以不选),问答案有多少种可能。

首先此题有一个$r-l\le 10000$的部分分很显然,只要把所有数丢到线性基里就ok了。

现在我们考虑正解。

我们发现当一个数可以被比它小的数表示时,就不需要加入线性基中。接下来我们考虑减少加入线性基中的数字数量。

我们发现对于两个相邻的数,$(2n)\oplus(2n+1)=1(n\in \mathbb{N})$。

所以我们找到$[l,r]​$中的第一个偶数(设为$x​$),则从$x+3​$开始的所有奇数都可以被表示为

其中$y$为奇数。

这样在$[l,r]$的所有奇数中,只有$x-1$和$x+1$无法被这样表示。

以此类推,所有$\%4=2$的数也都是一样的:我们先找到第一个四的倍数$x$,然后把$x-2$和$x+2$加入线性基。

这样我们最多只需要加入$64\times 2$个数就ok了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstring>

long long Base[65],n,l,r;
void add(long long tem){
for(int k=62;~k;--k)
if(tem&(1ll<<k)){
if(!Base[k]){
Base[k]=tem;
return;
}
tem^=Base[k];
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&l,&r);
long long ans=0,min=l;
memset(Base,0,sizeof Base);
for(long long x=2;(x>>1)<=r;x<<=1){
if(min%x)min+=(x>>1);
if(((min-(x>>1))>=l)&&((min-(x>>1))<=r))add(min-(x>>1));
if(((min+(x>>1))>=l)&&((min+(x>>1))<=r))add(min+(x>>1));
}
for(int k=62;~k;--k)if(Base[k])++ans;
printf("%lld\n",1ll<<ans);
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×