まず、必要条件について考える。

\(1\)以上\(D\)以下の各整数\(k\)について、\(1\)回の操作で\(A_k\), \(A_{D+k}\), \(\cdots\), \(A_{\left( \left[\frac{n-k}{D}\right]D+k\right) }\)のうちちょうど\(1\)つに対して操作が行われることに注意する。 さらにその操作について\(X\)の値が偶数であれば変更された値の偶奇は変化せず、奇数であれば偶奇は変化する。 このことから, \(P_k\)を\(P_k=A_k+A_{D+k}+\cdots +A_{\left( \left[\frac{n-k}{D}\right]D+k\right) }\)で定めると, 相異なる\(k_1\), \(k_2\)について, \(P_{k_1}\)および\(P_{k_2}\)の偶奇が一致しているか否かは変化しない。 よって、\(Q_k=B_k+B_{D+k}+\cdots +B_{\left( \left[\frac{n-k}{D}\right]D+k\right) }\)で定めると、最終状態では\(P_k+Q_k\)は全て偶数であるから、初期状態においても\(P_k+Q_k\)はすべて偶数であるかすべて奇数であるかのどちらかでなければならない。

また、\(N<2D-1\)のとき\(A_{N-D+1},\ldots ,A_D\)の範囲は全ての操作に含まれるからこれらには同じ操作が行われ、\(i=N-D+1,\ldots ,D\)に対して\(A_i+B_i\)がすべて一致しているか、\(B_i-A_i\)がすべて一致しているかの少なくとも一方が成り立っている必要がある。

逆にこの2つがみたされているとき\(N\)回で一致させることが可能なことを示す。

\(D=1\)のときは明らかなので、以下\(D\geqq 2\)とする。

まず、\(N=2D-1\)のとき可能なことを示す。

[\(1\),\(D\)],[\(2\),\(D+1\)],\(\ldots\),[\(D-1\),\(2D-2\)],[\(D\),\(2D-1\)],[\(D-1\),\(2D-2\)],\(\ldots\),[\(1\),\(D\)]の\(2D-1(=N)\)回の操作で一致させることを考える。 それぞれの操作における\(X\)の値を\(x_1\),\(x_2\),\(\ldots\),\(x_{2D-1}\)とし、\(i=1,\ldots ,D-1\)に対して,\(s_i\),\(t_i\)を\(s_i=x_i+x_{2D-i}\),\(t_i=x_{2D-i}-x_i\)で定める。 一方、\(S_i\), \(T_i\)を\(S_i=A_i+B_i\), \(T_i=B_i-A_i\)で定めると、これらの操作が\(A\)と\(B\)を一致させる条件は

\(T_1=t_1\)

\(T_2=t_1-t_2\)

\(\ldots\)

\(T_{D-1}=t_1-t_2\ldots (-1)^Dt_{D-1}\)

\(S_D=s_1-s_2+\ldots+(-1)^Ds_{D-1}+(-1)^{D+1}x_D\)

\(\ldots\)

\(S_{2D-2}=s_{D-1}-x_D\)

\(S_{2D-1}=x_D\)

となり、\(s_i\),\(t_i\),\(x_D\)についてこれを整理すると、

\(t_1=T_1\)

\(t_2=T_1-T_2\)

\(t_3=T_3-T_2\)

\(\ldots\)

\(t_{D-1}=(-1)^D(T_{D-1}-T_{D-2})\)

\(s_1=S_D+S_{D+1}\)

\(s_2=S_{D+1}+S_{D+2}\)

\(\ldots\)

\(s_{D-1}=S_{2D-1}+S_{2D-2}\)

\(x_D= S_{2D-1}\)

となる。

\(A\),\(B\) が\(1\)つめの必要条件をみたしていることから各\(i\)について\(s_i\)と\(t_i\)の偶奇は一致しており、このとき\(x_i\)と\(x_{2D-i}\)は整数となる。また上の式から\(x_D\)も求まりこのとき条件をみたすような構成ができた。 また、任意の\(i\)について\(\lvert A_i\rvert ,\lvert B_i\rvert \leqq M\)であるとき、各\(x_i\)の絶対値は\(4M\)で抑えられ、特に\(10^{13}\)以下となる。

次に、\(N>2D-1\)のときは前から\(i=1,\ldots ,N+1-2D\)についてこの順に[\(i\),\(i+D-1\)]に対して\(A_i\)と\(B_i\)が一致するように操作を行い、その後\(A_{N-2D+2},\ldots ,A_N\)に対して上と同様にすれば良い。

必要条件で述べた\(P_k\), \(Q_k\)の偶奇が一致しているかについては不変量であること、すでに最初の\((N-2D+1)\)項は一致しており、\(A_i\)と\(B_i\)の和や差は偶数となっていることに注意すると、この後ろ\(2D-1\)項に対して必ず上の操作を行うことができる。 このとき、操作回数は\(N+1-2D+2D-1=N\)回となる。 また、任意の\(i\)について\(\lvert A_i\rvert\),\(\lvert B_i\rvert\leqq M\)であるとき、\(N+1-2D\)回の操作の後の各\(A_i\)の絶対値は\(4M\cdot \frac{N}{D}\)で上から抑えられるから、\(X\)の値も出力の条件をみたしている。

最後に、\(N\leqq 2D-2\)のときは\(2\)つめの条件をみたしていることから\(i=N-D+1,\ldots D\)について\(A_i+B_i\)または\(B_i-A_i\)が一致している。後者の場合には[\(1,D\)]に対して\(X=0\)で操作を行う事で、\(A_i+B_i\)が一致しているケースに帰着できる。そしてこのとき、これらの要素を\(1\)つにまとめ、\(D'=N-D+1\)、\(N'=2D'-1\)の場合として解くことができる。

このときも回数は高々\(1+2(N-D+1)-1\leqq N\)回となっている。 最初の操作で\(A_i\)の絶対値が変化することはないからやはり\(x_i\)の値も条件をみたす。

よって、いずれの場合も\(N\)回以内で一致させられることが示された。

計算量について、判定や\(N\leqq 2D-1\)のときの構築は\(O(N)\)でできる。 \(N>2D-1\)のときは愚直にシミュレーションすると\(O(ND)\)程度かかってしまうが、遅延セグ木に乗せることで\(O(N\log N)\)、累積和のような処理をすることで\(O(N)\)で処理でき、十分高速である。