解説 · 720

解説

説明では添字を $0$ から $N-1$ までとし、すべての添字を $N$ を法として解釈する。

同じ開始位置で操作を二回行うと打ち消し合う。したがって、位置 $i$ から始まる操作を奇数回使うかどうかを $x_i\in\{0,1\}$ とすればよい。

位置 $i$ を最終的に 0 にするための条件は

a_i=\bigoplus_{j=i-K+1}^{i}x_j

である。隣接する二つの式を XOR すると

x_i\oplus x_{i-K}=\Delta_i,\qquad \Delta_i=a_i\oplus a_{i-1}

を得る。

$d=\gcd(N,K)$ 、 $m=N/d$ 、 $h=K/d$ とする。写像は、添字を長さのちょうど個の巡回に分解する。

剰余類 $r$ に対して

P_r=\bigoplus_{i\equiv r\pmod d}a_i

と定義する。一つの巡回に属する差分式をすべて XOR した値は $P_r\oplus P_{r-1}$ である。したがって差分式が矛盾なく解けるための必要十分条件は

P_0=P_1=\cdots=P_{d-1}

である。

一つの巡回を

v_t=r+tK\pmod N,\qquad t=0,\ldots,m-1

の順に並べる。canonical 解を

x_{v_0}=0,\qquad x_{v_t}=x_{v_{t-1}}\oplus\Delta_{v_t}\quad(t\ge1)

とする。巡回 $r$ に含まれる $x=1$ の個数を $c_r$ とする。

差分式だけを見ると、各巡回全体を反転する自由変数 $y_r$ が一つある。 $y_r=0$ のコストは $c_r$ 、のコストはである。よって差分式だけを満たす最小コストは

B=\sum_r\min(c_r,m-c_r)

である。

差分式は元の式同士の差しか使っていないため、元の式をもう一つ満たす必要がある。位置 $0$ の式に対して

E=a_0\oplus\bigoplus_{j=-K+1}^{0}x_j

とおく。必要なのは $E=0$ である。

長さ $K$ の区間には、各剰余類からちょうど $h=K/d$ 個の位置が含まれる。

$h$ が偶数なら、巡回全体を反転しても $E$ は変化しない。したがって $E=1$ なら不可能であり、 $E=0$ なら答えは $B$ である。

$h$ が奇数なら、各 $y_r$ は $E$ を一回反転するので

y_0\oplus y_1\oplus\cdots\oplus y_{d-1}=E

が必要である。各巡回でコストが小さい側を

z_r=[c_r>m/2],\qquad Z=\bigoplus_r z_r

とする。 $Z=E$ なら答えは $B$ である。そうでなければ一つの巡回で反対側を選ぶ必要があり、追加コストは

\min_r|m-2c_r|

である。

クエリで $a_p$ を反転すると、 $\Delta_p$ と $\Delta_{p+1}$ だけが反転し、だけが反転する。したがってである剰余類の個数を持てば、すべてのが等しいかをで判定できる。

巡回内で $\Delta_{v_s}$ を反転すると、 $s\ge1$ のとき canonical 解の

x_{v_s},x_{v_{s+1}},\ldots,x_{v_{m-1}}

という suffix がすべて反転する。 $s=0$ の $\Delta_{v_0}$ は巡回を閉じる整合条件にだけ使われるため、canonical 解自体は変化しない。

各巡回を巡回順に連結した長さ $N$ の配列を作り、区間反転と区間内の $1$ の個数を扱う lazy segment tree を用いる。各クエリでは suffix 反転は高々二回で、影響を受けた巡回の $c_r$ だけを再計算すればよい。

$c_r$ が変化するたびに、次を同時に管理する。

$E$ も毎回再計算する必要はない。 $\Delta_u$ を反転したときに変化する canonical suffix と、 $E$ に使う長さ $K$ の区間との共通部分の個数の偶奇を $impact[u]$ として前計算する。巡回の先頭ではである。位置のクエリでは

E\mathrel{\oplus}=[p=0]\oplus impact[p]\oplus impact[p+1]

と更新できる。

以上より各クエリの答えは次の通りである。

各テストケースの前処理は $O(N\log N)$ 、各クエリは $O(\log N)$ である。全体の計算量は $O((N+Q)\log N)$ 、メモリ使用量はである。

Solution written by GPT5.6