题意:
求区间$[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 longusing namespace std;
ll dp[maxn][][][][],d1[maxn],d2[maxn];inline ll read(){
ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}inline ll dfs(ll now,int t1,int t2,int q1,int q2){
if(now==-) return ;
if(dp[now][t1][t2][q1][q2]!=-) return dp[now][t1][t2][q1][q2];
int u1=t1?d1[now]:,u2=t2?d2[now]:; ll res=;
for(int i=;i<=u1;i++)
for(int j=;j<=u2;j++){
if(i== && j==) continue;
int nt1=t1&&(i==u1);
int nt2=t2&&(j==u2);
int nq1=q1||(i==);
int nq2=q2||(j==);
res+=dfs(now-,nt1,nt2,nq1,nq2);
}
dp[now][t1][t2][q1][q2]=res;
return res;
}inline ll calc(ll x,ll y){
if(x< || y<) return ;
memset(dp,-,sizeof(dp));
for(ll i=;i<=;i++) d1[i]=((x>>i)&);
for(ll i=;i<=;i++) d2[i]=((y>>i)&);
return dfs(,,,,);
}int main(){
ll T=read();
while(T--){
ll l=read(),r=read();
printf("%I64d\n",calc(r,r)-*calc(l-,r)+calc(l-,l-));
}
return ;
}
F