Kaho's Xor Query

2 secs 1024 MB
hide's icon hide

大きく分けて22通りの回答があると思います.

(1)桁に関するDP.(1) 桁に関するDP. 前計算O(N)O(N)のもとで,クエリあたりO(K)O(K).

(2)XOR(2)XORに関する性質を用いた数式計算.クエリあたりO(1)O(1).

いずれでも実行時間には余裕があると思います.以下それぞれに関する簡単な説明を記します.


(1)桁に関するDP.(1) 桁に関するDP.

LA1A2......ANRL \le A_1 \oplus A_2 \oplus ... ... \oplus A_N \le Rの代わりに

A1A2......ANR A_1 \oplus A_2 \oplus ... ... \oplus A_N \le Rの個数 ・・・(#)

を数えることを考えます.これが解決できれば元の問題も

同様に解決できることは明らかです.

以下,(#)を解決することを考えます.

さて,RR以下の数は,「RRと比較した時,初めてbitbitが優位に小さくなる最上位桁」でグループ分けできます。

例を挙げるとR=11010(2)R = 11010(2)の時(0????),(10???),(1100?),(11010)(0????),(10???),(1100?),(11010)のようなグループに分けることができます.

この時,??0,1{0,1}どちらでもよいです.

さて,i(bit)i(bit)目が0,1{0,1}であるかどうかは,iiに非依存であり,それぞれが

i is evencomb(N,i),i is oddcomb(N,i)\sum_{i\ is\ even}^{} comb(N,i),\sum_{i\ is\ odd}^{} comb(N,i)

であることはXORXORの定義から明らかです.

従って,最上位bitbitからグループを走査してゆくことで,動的計画法の要領で(#)O(K)O(K)で求めることができます.

以上のことから,二項係数テーブルをO(N)O(N)で構築のもと,各クエリにはO(K)O(K)で回答することができます.


(2)XOR(2)XORに関する性質を用いた数式計算.クエリあたりO(1)O(1).

実は,A1A2......AN=iA_1 \oplus A_2 \oplus ... ... \oplus A_N = iを満たす数列の個数はiiによらず2K(N1)2 ^ {K(N - 1)}です.

なぜなら,これは前半N1N - 1項を適当に決めることに相当し,そのいずれにおいても残る11項は一意に定まるからです.

以上より求める個数は (RL+1)2K(N1)(R - L + 1) 2 ^ {K(N - 1)}です.

2K(N1)2^{K(N - 1)}はクエリ全体を通して固定ですのでこれを前計算しておけばクエリごとO(1)O(1)です.