Atcoder regular contest 133 d.range XOR (digital dp+ classification discussion)

subject

Given L,R,V(1<=L<=R<=1e18,0<=V<=1e18)

Please L<=l<=r<=R, And (l,r) The exclusive or sum of numbers between is exactly equal to v Of (l,r) Number of two tuples ,

The answer is right 998244353 modulus

Source of ideas

YLWang Code

Answer key

heltion Of dp Unify all situations , But I can't understand orz, Just fill this

Official explanation , It's also digital dp+ Classification of discussion

be aware [0,x] There are only four prefix XOR values ,

①x%4==0 when , by x

②x%4==1 when , by 1

③x%4==2 when , by x+1

④x%4==3 when , by 0

[l,r] Exclusive or and , That is, prefix exclusive or and sum[r]^sum[l-1]

Then points l-1 model 4 Value ,r model 4 Value ,16 There are two situations to discuss

What is more difficult to deal with are the following four situations ：

①(l-1)%4=0 And r%4=0

②(l-1)%4=0 And r%4=2

③(l-1)%4=2 And r%4=0

④(l-1)%4=2 And r%4=2

rest 12 In this case ,

Or you can determine the location of an endpoint ,

Or it's like an arithmetic sequence , Can be obtained quickly

this 4 In this case , It can be reduced to one problem ,

That is, given interval [x,y], Extract two unequal numbers from the interval lb,rb(lb<rb), seek lb^rb=w Binary logarithm of (lb,rb)

there x the truth is that l-1, and y Still r

therefore , Introduce digits dp,

dp[i][j][k] It means that there is still i position , The first number is / No card upper bound , Whether the second number is the number of schemes of the upper bound of the card

One dimensional digits dp, It's usually used dfs(r)-dfs(l-1), Prefix subtraction to find the answer

The same goes for two dimensions , Because it can only control the upper bound of card or not , So the problem of the lower bound of the card is left to Rong Xu ,

Similar to two-dimensional matrix solution (l,l) To (r,r) The area of , Subtract two rectangular areas from the total area , Add back the area of the rectangle in the upper left corner

Analogy shows that , The final two-dimensional answer is solve(r,r)-2*solve(l-1,r)+solve(l-1,l-1)

Due to the fact that l-1<r, So when v=0 when , You need to extract any equal number (l-1==r) Subtract the number of ,

And because of the number dp in ,i and j It's symmetrical , It doesn't matter , So the final answer is divided by 2

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,mod=998244353,inv2=(mod+1)/2;
ll l,r,v;
int ans,a[66],b[66],dp[66][2][2];
void add(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
    if(x<0)x+=mod;
}
int dfs(int pos,bool lima,bool limb,ll my_v){
	if(pos==-1){
        return 1;
	}
	if(~dp[pos][lima][limb])return dp[pos][lima][limb];
    int ret=0;
    int upa=lima?a[pos]:1,upb=limb?b[pos]:1;
    for(int i=0;i<=upa;++i){
        for(int j=0;j<=upb;++j){
            if(pos==0 && (i || j))continue;//l:(0,2) r:(0,2)
            if(pos==1){
                if((i^j) && (v%4!=3))continue;//l:0 r:2; l:2 r:0
                if((i==j) && (v%4!=0))continue;//l:0 r:0; l:2 r:2
            }
            if((i^j) != (my_v>>pos&1))continue;
            add(ret,dfs(pos-1,lima && i==upa,limb && j==upb,my_v));
        }
    }
    dp[pos][lima][limb]=ret;
    return ret;
}
int solve(ll x,ll y,ll v){
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
	int sza=0,szb=0;
	for(;x;x/=2)a[sza++]=x%2;
    for(;y;y/=2)b[szb++]=y%2;
    memset(dp,-1,sizeof dp);
    return dfs(63,1,1,v);
}
int cal(ll lb,ll rb,int re){
    if(rb<re || lb>rb)return 0;
    ll nowl=0,nowr=0;
    nowr=(rb-re)/4+1;
    lb--;
    if(lb<re)nowl=0;
    else nowl=(lb-re)/4+1;
    ll ans=nowr-nowl;
    ans%=mod;
    return (int)ans;
}
//[lb,rb] Internal extraction l<=r, bring (l^r)==v Logarithm of number , Special judgement lb=0
int cal2(ll lb,ll rb,ll v){
    int ans=0;
    ans=((1ll*solve(rb,rb,v)-2ll*solve(lb-1,rb,v)+solve(lb-1,lb-1,v))%mod+mod)%mod;
    if(!v){//l=r illegal ,l It's practical l-1
        ans=(ans-cal(lb,rb,0)+mod)%mod;
        ans=(ans-cal(lb,rb,2)+mod)%mod;
    }
    ans=1ll*ans*inv2%mod;
    return ans;
}
int main(){
    scanf("%lld%lld%lld",&l,&r,&v);
    if(v==0){
        int three=cal(l-1,r,3);//l-1:3 r:3 C(x,2)
        add(ans,1ll*(three-1)*three%mod*inv2%mod);
        int one=cal(l-1,r,1);//l-1:1 r:1 C(x,2)
        add(ans,1ll*(one-1)*one%mod*inv2%mod);
    }
    if(v==1){
        int two=cal(l,r,2);
        if(two){//l-1:1 r:3
            ll ltwo=l;while(ltwo%4!=2)ltwo++;
            int lthree=cal(ltwo,r,3);
            ll rtwo=r;while(rtwo%4!=2)rtwo--;
            int rthree=cal(rtwo,r,3);
            add(ans,1ll*(lthree+rthree)*two%mod*inv2%mod);
        }
        int zero=cal(l,r,0);
        if(zero){//l-1:3 r:1
            ll lzero=l;while(lzero%4)lzero++;
            int lone=cal(lzero,r,1);
            ll rzero=r;while(rzero%4)rzero--;
            int rone=cal(rzero,r,1);
            add(ans,1ll*(lone+rone)*zero%mod*inv2%mod);
        }
    }
    if(v%4==0){
        if(l<=v+1 && v+1<=r){
            add(ans,cal(v+1,r,3));//l-1:0 r:3
        }
        if(l<=v && v<=r){
            add(ans,cal(l,v,0));//l-1:3 r:0
        }
        if(l>1)add(ans,cal2(l-1,r,v));//l-1:0 r:0 l-1:2 r:2
        else add(ans,cal2(1,r,v)+(l<=v && v<=r));// Special judgement l-1=0, Split into two parts for statistics 
    }
    if(v%4==1){
        if(l<=v && v<=r){
            add(ans,cal(v,r,1));//l-1:0 r:1
        }
        if(l<=(v^1) && (v^1)<=r){
            add(ans,cal(l,v^1,2));//l-1:1 r:0
        }
    }
    if(v%4==2){
        if(l<=v && v<=r){
            add(ans,cal(l,v,2));//l-1:1 r:2
        }
        if(l<=(v^1) && (v^1)<=r){
            add(ans,cal(v^1,r,1));//l-1:2 r:1
        }
    }
    if(v%4==3){
        if(l<=v && v<=r){
            add(ans,cal(v,r,3));//l-1:2 r:3
        }
        if(l<=(v^1) && (v^1)<=r){
            add(ans,cal(l,v^1,0));//l-1:3 r:2
        }
        if(l>1)add(ans,cal2(l-1,r,v^1));//l-1:0 r:2;l-1:2 r:0
        else add(ans,cal2(1,r,v^1)+(l<=(v^1) && (v^1)<=r));// Special judgement l-1=0, Split into two parts for statistics 
    }
    printf("%d\n",ans);
    return 0;
}