kojingharangの日記

SRM 453 Div1 250 EllysXors

03:40 |

• L～R の XOR を求める問題。1 <= L, R <= 4,000,000,000

• 1～2**N-1 の XOR は 0 になるっぽい
• L～R の XOR は 1～L-1 の XOR と 1～R の XOR の XOR になるっぽい
• なので、1～n の XOR を求める f(n) を作る

• 最上位ビットを見つけて 2**N <= n < 2**(N+1) な N を見つけたら、2**N より小さい範囲の XOR は 0
• 2**N から n までは、最上位ビットに関しては n - 2**N の偶奇で XOR の結果がわかる
• それと f(最上位ビットを消した値) の XOR を再帰的にとる

• あれ f(2) が 3 になるぞ　大きな値で試したりして、よくわからないけど 2 のときだけこうなるっぽい
• 10未満のときは定義通り計算することにする

• いろいろ証明できてないので100までで定義通りの計算結果と一致することを確認

• passed system test

ll ff(ll v) {
	ll ans=0;
	for(ll i=1;i<=v;i++) ans^=i;
	return ans;
}

ll f(ll v) {
	if(v<10) return ff(v);
	ll a=1;
	while(v>a) a=a<<1;
	a>>=1;
	return (((v-a)&1) ? 0 : a) ^ f(v^a);
}

class EllysXors {
	public:
	long long getXor(long long L, long long R) {
		//REP(i, 100) if(f(i+1)!=ff(i+1)) cout<<"ERRO"<<endl;
		return f(R)^f(L-1);
	}
};

• ちなみに unsigned int にして単純なループで通してる人がいた。
• 手元で実行したら 3400ms くらい。
• ほほ～

ll fff(ll A, ll B) {
	unsigned ans=0;
	unsigned AA = A;
	unsigned BB = B;
	for(unsigned i=AA;i<=BB;i++) ans^=i;
	return ans;
}

ツイートする