考虑简单的容斥
设 $F(n,m)$ 表示 $a in [1,n] , b in [1,m]$ 的满足 $a+b=a ext{ xor } b$ 的数对的数量
那么答案即为 $F(r,r)-2F(l-1,r)+F(l-1,l-1)$
意思就是总方案减去 $a,b$ 至少一个数小于 $l$ 再加上 $a,b$ 都小于 $l$ 的方案
然后现在考虑求 $F$
首先显然 $a+b=a ext{ xor } b$ 意思就是二进制下不存在同时为 $1$ 的位
那么可以考虑简单的数位 $dp$，设 $f[i][0/1][0/1]$ 表示从高到低位填了 $i$ 位，$a$ 是否贴着上限 $n$ ， $b$ 是否贴着上限 $m$ ，时的合法数对 $a,b$ 的方案数
那么转移就枚举下一位 $a$ 填的 $0$ 还是 $1$ ， $b$ 填的 $0$ 还是 $1$ ，顺便保证一下满足限制就行了
代码参考：jiangly
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } ll solve(int n,int m)//注意此时的n,m是开区间 { if(n<0||m<0) return 0; ll f[2][2][2]; int p=0; f[p][0][0]=f[p][0][1]=f[p][1][0]=0; f[p][1][1]=1; //0表示没贴着上限,1表示贴着上限 for(int i=30;i>=0;i--) { p^=1; memset(f[p],0,sizeof(f[p]));//滚动数组 for(int ln=0;ln<=1;ln++) for(int lm=0;lm<=1;lm++) for(int x=0;x<=1;x++) for(int y=0;x+y<=1;y++) if( ((!ln)||x<=((n>>i)&1)) && ((!lm)||y<=((m>>i)&1)) ) f[p][ln & ( x == ((n>>i)&1) )][lm & ( y == ((m>>i)&1) )] += f[p^1][ln][lm]; } return f[p][0][0];//不包括恰好等于n,m的情况 } int main() { int T=read(); while(T--) { int l=read(),r=read(); printf("%lld ",solve(r+1,r+1)-solve(l,r+1)*2+solve(l,l));//开区间,右端点集体+1 } return 0; }