中盤で手間取って時間を残せなかったのが敗因。
https://atcoder.jp/contests/arc133/tasks/arc133_d
問題
整数L,R,Vが与えられる。
L≦l<r≦Rとなる(l,r)の組のうちlからrまでの整数のxorを取るとVとなるようなものは何通りか。
解法
f(x) := 0~(x-1)までのxorを取ったもの
とすると、f(l) xor f(r+1) = VとなるL≦l<(r+1)≦Rと探すことになる。
ここで、
- x=4k+0のときf(x) := 0
- x=4k+1のときf(x) := 4k+1
- x=4k+2のときf(x) := 3
- x=4k+3のときf(x) := 4k
となる。
そこで、lと(r+1)の下2bitを4通りずつ総当たりすることを考える。
l=4n+a
r+1=4m+b
としたとき、f(a) xor f(b)の下2bitがVの下2bitと一致するとき、L/4≦n≦m≦(R+1)/4(a≧bならn<m)を満たす範囲で、n,mの各bitの値を上から埋めて行こう。
ll L,R,V; const ll mo=998244353; ll memo[66][2][2][2]; ll A,B; int va,vb; int beless; __int128 hoge(int ta,int tb,int le,int d) { if(d==1) { return beless==0||le==1; } ll& ret=memo[d][ta][tb][le]; if(ret>=0) return ret; ret=0; int x,y; FOR(x,2) FOR(y,2) { int v=(x&va)^(y&vb); if((V>>d)%2!=v) continue; if(le==0&&x>y) continue; if(ta==0&&x==0&&(A>>d)%2==1) continue; if(tb==0&&y==1&&(B>>d)%2==0) continue; ret+=hoge(ta||(x==1&&(A>>d)%2==0),tb||(y==0&&(B>>d)%2==1),le||x<y,d-1); } ret%=mo; return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>L>>R>>V; R++; ll ret=0; ll m[4]={0,0,1,3}; int valid[4]={0,1,0,1}; FOR(x,4) FOR(y,4) if((m[x]^m[y])==V%4) { A=L,B=R; while((A+0)%4!=x) A++; while((B+4)%4!=y) B--; if(A>=B) continue; va=valid[x]; vb=valid[y]; beless=x>=y; MINUS(memo); ret+=hoge(0,0,0,60); } cout<<ret%mo<<endl; }
まとめ
うーん、本番中詰め切れなかった…。