とりあえず、 \((A_1 \times A_2)\oplus (A_2\times A_3)\oplus \ldots \oplus (A_{N-1} \times A_N)\) の \(2\) 進数での \(M-1\)(0-indexed) 桁目が \(1\) になる \(A\) の個数を数え上げることにしましょう。

ここで、関数 \(f\) を \(A\) の \(M-1\) 桁目が \(0\) ならば \(f(A)=-1\) 、 \(1\) ならば \(f(A)=1\) として \(f(A)\) の合計を考えることにします(ここから元の個数は復元できます)

この時、以下が成り立ちます :

• ある偶数 \(i\) が存在して \(A_i\) が奇数であるような数列の集合を \(S\) とする。このとき、 \(\sum_{a \in S} f(a) = 0\) である。

証明 : \(S\) に含まれる数列 \(A\) に対し、 \(f(g(A)) +f(A)=0\) かつ \(g(A) \in S\) かつ \(g(g(A))=A\) となるような \(g\) を構成することを考える。\(S\) に含まれているという条件より、 \(A_{i-1}+A_{i+1}\) (存在しないものは \(0\)) が奇数であるような奇数 \(i\) が存在するはず。ここで、 \(A_i\) を \(A_i \oplus 2^{M-1}\) に置き換えた数列を \(g(A)\) とすると、これは条件を満たす。

次に、 \(S\) に含まれない (\(A_2,A_4,\ldots\) がすべて偶数である)数列について考えます。ここで、 \(A_1,A_3,\ldots\) の最上位桁、 \(A_2,A_4,\ldots\)の最下位桁が解に一切寄与していないことに着目すると、先ほどと同じようなことが成り立ちます。

• \(A_2,A_4,\ldots\) がすべて偶数かつ、ある偶数 \(i\) が存在して \(A_i\) が \(4\) で割り切れないような数列の集合を \(S\) とする。このとき、 \(\sum_{a \in S} f(a) = 0\) である。

証明は最初と同じなので略します。これは繰り返し適用することができるため、結局 \(A_2,A_4,\ldots\) がすべて \(0\) でないようなものについての \(f(A)\) の和は \(0\) です。 \(A_2,A_4,\ldots\) がすべて \(0\) のとき、 \(f(A)=-1\) ですから、 \(M-1\) 桁目の寄与が \(O(\log N+\log M)\) で求められます。 \(k\) 桁目の寄与は \(M=k+1\) の時の問題に適当な係数をかけたものとして表現できますから、この問題を \(O(M(\log N + \log M))\) で解くことができます。また、式を変形することで \(O(\log N + \log M)\) 程度でも解くことができます。

想定解