题面。
A.
原题 AGC015D。
两个题目实质上是一样的。。。
分析一手这个异或和中每一位的贡献。
发现这一位的数字上只要存在 1，这一位的贡献就是 $2^{n-1}\times 2^p$，其中 $p$ 是这一位的位数。
于是问题就转化成了不多于 $n$ 个数字或在一起能得到的值的种类数。
然后我只会暴力，交完走人。
后来才知道直接撞车，原来 ZR 人均能切 AGCD。。。
其实这个 $n$ 在 $n>2$ 和 $n=2$ 是同一个情况，$n=1$ 的时候特判一下就完了。
为什么 $n>2$ 与 $n=2$ 等价，可以设如果一个数由多个数或起来构成，那必然可以找到一个最高位不同的两个数字，然后我们可以把那位为 0 的数字或上剩下的数字，结果和多个数字还是一样的。
接下来讨论一下具体做法。
显然，对于 $l$ 和 $r$ 这两个数，高位全部相同就完全不用考虑。
我们找到从高到低第一个不同的位置，称之为 $p$。
因为 $r>l$，显然这一位满足 $r$ 在位置 $p$ 上是 1，而 $l$ 在位置 $p$ 上是 0。
接下来就是人类智慧构造。
举个例子：
1
2
3
4
5
6
7
8
9
10
11
| 这个是 r：
1101... 1 ...1010
相同的高位 p 剩余的低位
这个是 l：
1101... 0 ...0011
相同的高位 p 剩余的低位
构造这个 z：
1101... 1 ...0000
相同的高位 p 剩余的低位全部是 0
|
然后这个 $z$ 可以用来干什么？
如果我们把 $[l,r]$ 用 $z$ 分成 $[l,z)$ 和 $[z,r]$。
那么 $[z,r]$ 这个区间内相互或可以得到 $[z,q]$ 的所有整数。
1
2
3
| 这个 q 就是：
1101... 1 00... 111...111
相同的高位 p 全是 0 r 在 p 之后的第一个 1，后面全是 1
|
这个很容易想。并且 $q$ 是最大值。
同时 $[l,z)$ 可以产生的数显然还是 $[l,z)$。
最后两个区间交叉或的话，显然最小值是 $l\operatorname{or} z$。而最大值就是 $z\operatorname{or}(z-1)$（这个显然大于等于 $r$ 也大于等于 $q$）。而且显然最大值与最小值之间的连续值是都可以取到的。
然后我们最后答案的区间就是 $[l,q]\cup [l\operatorname{or}z,z\operatorname{or}(z-1)]$。
然后我们只要分类一下 $q$ 与 $l\operatorname{or} z$ 的大小关系输出就完了。
时间复杂度 $O(T\log v)$。
代码：
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=5e2;
ll T,n,l,r;
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {write(x);putchar(10);}
int main() {
T=read();
while(T--) {
n=read();l=read();r=read();
if(n==1) {writeln(r-l+1);continue;}
if(l==r) {writeln(1);continue;}
ll pos=0,z=0,ans=0;
for(ll i=62;i>=0;i--) {
if(((l>>i)&1)!=((r>>i)&1)) {z=(r>>i)<<i;pos=i;break;}
}
ll r1=z,l2=l|z,r2=z|(z-1);
for(ll i=pos-1;i>=0;i--) {
if((r>>i)&1) {r1=z|((1ll<<(i+1))-1);break;}
}
if(r1<l2) ans=(r1-l+1)+(r2-l2+1);
else ans=r2-l+1;
writeln(ans);
}
return 0;
}
|
B.
咕。
C.
咕。