考慮すべき $X$ の個数がとんでもない数になりそうだが、実は多くはXORで打ち消しあって消える。
合計が同じになる、要素を並び替えただけの2つの $X$ 同士は打ち消しあうため、考慮しなくてよい。
たとえば $K=11$ 個から、$A_1$ を $3$ 個、$A_3$ を $4$ 個、$A_5$ を $4$ 個選ぶような $X$ の個数は、
多項係数 $\dfrac{11!}{3! \times 4! \times 4!}$ で求められる。
これが偶数になるような選び方は考慮しなくてよいことになる。
また、奇数の時も打ち消しあって残った1個のみ考慮すればよい。
では、奇数になるのはどんなとき?
これは、Lucasの定理を使える。
特にmod2、nCr の偶奇を知りたいときは、以下が成り立つ。
今回の場合もこれを連鎖的に適用すると、以下が成り立つ。
これを言い換えると(なかなか直感的には言い換えるのが難しく思うが)、
「$K$ の2進数表記で立っているbitごとに、$A_1~A_N$ のどれかから選んでbitshiftして足し合わせる」ような操作で作られる数が、並べ替えの個数が奇数となるような $X$ に対する $f(X)$ となる。
K = 1011 ※K,Aiは2進数表記 A = (10, 11, 101) 1の位 10の位 1000の位 f(X) 加算するAiの内訳 o-- + 10 --- + 10*0 --- + 10*000 → 10110 10を11個 | | |--- + 11*000 → 11110 10を 3個、 11を 8個 | | `--- +101*000 → 101110 10を 3個、101を 8個 | |--- + 11*0 --- + 10*000 → 11000 10を 9個、 11を 2個 | | |--- + 11*000 → 100000 10を 1個、 11を10個 | | `--- +101*000 → 110000 10を 1個、 11を 2個、101を 8個 | `--- +101*0 --- ... | |--- ... |-- + 11 --- ... `-- +101 --- ... ~~~~~~ 答えは、ここに来る全f(X)のXOR
答えを求める際には、この樹形図を縦に見て、下の桁から確定させていく。
1の位で答えの下1桁を求めたら、10や1000の位ではもう変化しないので、確定する。
次、10の位を考慮するにあたり、繰り上がりが発生する。
「10からは1」「11からは1」「101からは10」繰り上がるが、「1」繰り上がる2つに関しては、この後の樹形図が同じため打ち消し合う。
したがって、「10」のみが残る。繰り上がる数も、奇数個繰り上がるもののみを持っておけばよい。
10の位では、繰り上がってきた数それぞれに対して、各 $A_i$ を加算した集合(上例では100,101,111)で 同様に下1桁のXORを計算し、答えに反映する。
100の位では、$K$ でbitが立っていないため、($A_i$ は加算せず)繰り上がってきた数の集合のままで下1桁のXORを計算する。
($K$ で立っているbitを予め調べ、10の位とまとめて求めてもよい)
1000の位でも同様に、各繰り上がった数に各 $A_i$ を足す。
最後については下1桁でなく、$A_i$ 加算後の集合のそのままの値のXORを求め、bitshiftして答えに加算する。
最後は、$N$ が偶数でも加算してよい。
これで最終的な答えとなる。
各桁で繰り上がる数の種類数の上限は、$\dfrac{A_{max}}{2} \simeq 500$。
それぞれに $N$ 個の $A_i$ の加算を試す、ということを最大 $O(\log{K})$ 回おこなうため、計算量は $O(NA_{max}\log{K})$。