题意：询问区间[l,r]上有多少个有序对(a,b)满足a+b=a xor b
相加等于异或，言外之意就是两个数每一个二进制位上都不能同时为1，那就让两个数从最高位同时往下走好了，设两个数的f,g分别表示是否撞到上界或者下界，然后dp即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N=3e5+10,inf=0x3f3f3f3f; 5 ll dp[35][2][2][2][2]; 6 int l,r; 7 int main() { 8 int _; 9 for(scanf("%d",&_); _--;) { 10 scanf("%d%d",&l,&r); 11 memset(dp,0,sizeof dp); 12 dp[32][1][1][1][1]=1; 13 for(int u=32; u>=1; --u) 14 for(int f1=0; f1<=1; ++f1) 15 for(int g1=0; g1<=1; ++g1) 16 for(int f2=0; f2<=1; ++f2) 17 for(int g2=0; g2<=1; ++g2) 18 for(int i=0; i<=1; ++i) 19 for(int j=0; j<=1; ++j) { 20 if(i&&j)continue; 21 if(f1&&i>(r>>(u-1)&1))continue; 22 if(g1&&i<(l>>(u-1)&1))continue; 23 if(f2&&j>(r>>(u-1)&1))continue; 24 if(g2&&j<(l>>(u-1)&1))continue; 25 int f11=f1&&i==(r>>(u-1)&1); 26 int g11=g1&&i==(l>>(u-1)&1); 27 int f22=f2&&j==(r>>(u-1)&1); 28 int g22=g2&&j==(l>>(u-1)&1); 29 dp[u-1][f11][g11][f22][g22]+=dp[u][f1][g1][f2][g2]; 30 } 31 ll ans=0; 32 for(int f1=0; f1<=1; ++f1) 33 for(int g1=0; g1<=1; ++g1) 34 for(int f2=0; f2<=1; ++f2) 35 for(int g2=0; g2<=1; ++g2) 36 ans+=dp[0][f1][g1][f2][g2]; 37 printf("%lld\n",ans); 38 } 39 return 0; 40 }