题意：
求区间$[l,r]$内有多少有序数对$(a,b)$满足$a+b=a\bigoplus b$。
$l,r\leq 10^9$。
题解：
有用的就一句话：
求区间内一元组可以一维容斥，同理求二元组可以二维容斥，三元组可以三维容斥……
我tm原来居然不知道，佛了。
然后数位dp就完事了。
代码：
#include<bits/stdc++.h> #define maxn 55 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; ll dp[maxn][2][2][2][2],d1[maxn],d2[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘; return x*f; } inline ll dfs(ll now,int t1,int t2,int q1,int q2){ if(now==-1) return 1; if(dp[now][t1][t2][q1][q2]!=-1) return dp[now][t1][t2][q1][q2]; int u1=t1?d1[now]:1,u2=t2?d2[now]:1; ll res=0; for(int i=0;i<=u1;i++) for(int j=0;j<=u2;j++){ if(i==1 && j==1) continue; int nt1=t1&&(i==u1); int nt2=t2&&(j==u2); int nq1=q1||(i==1); int nq2=q2||(j==1); res+=dfs(now-1,nt1,nt2,nq1,nq2); } dp[now][t1][t2][q1][q2]=res; return res; } inline ll calc(ll x,ll y){ if(x<0 || y<0) return 0; memset(dp,-1,sizeof(dp)); for(ll i=0;i<=30;i++) d1[i]=((x>>i)&1); for(ll i=0;i<=30;i++) d2[i]=((y>>i)&1); return dfs(30,1,1,0,0); } int main(){ ll T=read(); while(T--){ ll l=read(),r=read(); printf("%I64d\n",calc(r,r)-2*calc(l-1,r)+calc(l-1,l-1)); } return 0; }
[cf 1245 F] Daniel and Spring Cleaning
原文：https://www.cnblogs.com/YSFAC/p/11785319.html
