kmjp's blog

競技プログラミング参加記です

AtCoder ARC #133 : D - Range XOR

中盤で手間取って時間を残せなかったのが敗因。
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;
}

まとめ

うーん、本番中詰め切れなかった…。