Codeforces1245 F.Daniel and Spring Cleaning（数位dp）

题意：

给定l，r，要求计算${\sum }_{a=l}^r{\sum }_{b=l}^r[a+b=a?b]$

数据范围：0<=l,r<=1e9

解法：

$令f(l,r)={\sum }_{a=0}^r{\sum }_{b=0}^r[a+b=a?b]$
$由容斥得ans=f(l,r)?f(l?1,r)?f(r,l?1)+f(l?1,l?1)$
$由于f(l,r)=f(r,l)，因此ans=f(l,r)?2?f(l?1,r)+f(l?1,l?1)$

考虑什么情况下a+b=a?b：
对于a和b的二进制下第k位x和y，当前仅当x和y不同时为1的时候满足x+y=x?y，
那么其实就是统计有多少对数(a,b)，满足二进制位每一位都不同时为1即可。

数位dp即可，同时枚举两个数。

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=2e5+5;
int L[33],R[33];
int d[33][2][2];
int len1,len2;
int dfs(int len,int l1,int l2){
    if(!len)return 1;if(d[len][l1][l2]!=-1)return d[len][l1][l2];int ans=0;int ma1=(l1?L[len]:1);int ma2=(l2?R[len]:1);for(int i=0;i<=ma1;i++){
    for(int j=0;j<=ma2;j++){
    if((i&j)==0){
    ans+=dfs(len-1,l1&&(i==ma1),l2&&(j==ma2));}}}d[len][l1][l2]=ans;return ans;
}
int solve(int l,int r){
    if(l<0)return 0;memset(d,-1,sizeof d);memset(L,0,sizeof L);memset(R,0,sizeof R);len1=len2=0;while(l){
    L[++len1]=l%2;l/=2;}while(r){
    R[++len2]=r%2;r/=2;}return dfs(len2,1,1);
}
signed main(){
    int T;cin>>T;while(T--){
    int l,r;cin>>l>>r;int ans=solve(r,r)-2*solve(l-1,r)+solve(l-1,l-1);cout<<ans<<endl;}return 0;
}