ABC121 D - XOR World(400)

D - XOR World

概要

非負整数A, Bに対し、f(A, B) = A XOR A+1 XOR ... XOR B とする。f(A, B)を求めよ。

制約

0 ≦ A ≦ B ≦ 10^12

方針

XORの逆操作はXOR自身なので、f(A, B) = f(0, B) XOR f(0, A)
よって0からXまでの累積XORを求めればよい。

0から数字を2進表記で記述してゆき、それとともに累積XORの数を記載してゆく。
表の左側が2進表記の数字Xを表し、右側が0からXまでの累積XORを表す。
なお、累積XORは2進表記の各桁ごとに独立して計算することができる。

0	0	0	0		0	0	0	0
0	0	0	1		0	0	0	1
0	0	1	0		0	0	1	1
0	0	1	1		0	0	0	0
0	1	0	0		0	1	0	0
0	1	0	1		0	0	0	1
0	1	1	0		0	1	1	1
0	1	1	1		0	0	0	0
1	0	0	0		1	0	0	0
1	0	0	1		0	0	0	1
1	0	1	0		1	0	1	1
1	0	1	1		0	0	0	0
1	1	0	0		1	1	0	0
1	1	0	1		0	0	0	1
1	1	1	0		1	1	1	1
1	1	1	1		0	0	0	0

観察すると各桁ごとに下記の規則性が見られる。

• 累積XORの右から0桁目はX = 1, 2 (mod 4)で1、それ以外は0
• 累積XORの右から1桁目はX = 2 (mod 4)で1、それ以外は0
• 累積XORの右から2桁目はX (mod 8) ≧ 4 かつ X = 0 (mod 2)で1、それ以外は0

…

• 累積XORの右からa桁目はX (mod 2^(a+1) ) ≧ 2^a かつ X = 0 (mod 2)で1、それ以外は0

このルールに従い、各桁ごとに累積XORを計算すればよい。

感想

公式解説では偶数nについて、n XOR n+1 = 1であることを使っていました。エレガント。

解答

Submission #4561459 - AtCoder Beginner Contest 121

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
ll calc(ll x){
	if(x == 0) return 0;
	int max_dig = 61;
	while(!((x >> max_dig) & 1)) max_dig--;
	// cout << max_dig << endl;
 
	ll ans = 0;
	for(int a = 0; a <= max_dig; a++){
		if(a == 0){
			if(x % 4 == 1 || x % 4 == 2){
				ans ^= 1;
			}
			continue;
		}
 
		if(a == 1){
			if(x % 4 == 2){
				ans ^= 2;
			}
			continue;
		}
 
		ll b = 1LL << a;
		ll c = x % (b * 2);
		if(c < b) continue;
		// cout << a << "," << (c - (b - 1)) % 2 <<"," <<  ((c - (b - 1)) % 2 << a) << endl;
		ans ^= (c - (b - 1)) % 2 << a;
	}
 
	return ans;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll A, B;
	cin >> A >> B;
	// cout << calc(A-1) << endl;
	// cout << calc(B) << endl;
	if(A == 0){
		cout << calc(B) << endl;
	}else{
		cout << (calc(A-1) ^ calc(B)) << endl;
	}
}