問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

整数列 $X=(X_1, \dots, X_n)$ が以下の操作を好きな回数だけ行うことで全ての項を $0$ にすることができるとき, $X$ は良い数列であるという.

$1 \leq i \leq n-K+1$ 及び整数 $c$ を選び, $X_i ,X_{i+1}, \dots, X_{i+K-1}$ の全てに $c$ を足す.

長さ $N$ の整数列 $A=(A_1, \dots, A_N)$ がある. 次の $Q$ 個の問に答えよ.

$A$ の第 $l_q$ 項から第 $r_q$ 項までの部分列は良い数列か?

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq \min(10, N)$
$-10^9 \leq A_i \leq 10^9$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq l_q \leq r_q \leq 10^9$
$r_q-l_q+1 \geq K$

解法 (1) 良い数列の特徴づけ

整数列 $X=(X_1, \dots, X_N)$ に対して, 以下は同値である.

$X$ は良い数列である.
$a=0,1, \dots, K-1$ に対して, $\displaystyle S_a:=\sum_{\substack{1 \leq i \leq N \\ i \equiv a \pmod{K}}} X_i$ とする. このとき, $S_0=S_1=\dots=S_{K-1}$ である.

(上) ならば (下)について, 各操作は可逆である. 連続する $K$ 個の項を $c$ 増やすことの逆操作は同じ連続する $K$ 個の項を $c$ 減らすことである. このとき, 連続する $K$ 個の整数 $i, i+1, \dots, i+K-1$ について, これを $K$ で割った余りは $0,1,2, \dots, (K-1)$ が $1$ 回ずつ登場する. よって, $S_0, \dots, S_{K-1}$ は全て $c$ だけ減る.

全ての項が $0$ であるとき, $S_0=S_1=\dots=S_{K-1}=0$ であるから, 初期状態においても $S_0=\dots=S_{K-1}=0$ である.

(下) ならば (上) について, 次のようにすることで, $K \lt i \leq N$ に対して, $X$ の第 $i$ 項を $0$ に, 第 $(i-K)$ 項を $X_{i-K}+X_K$ にすることができる.

$X$ の第 $(i-K+1), (i-K+2), \dots, (i-1), i$ 項全てに $-X_i$ を足す.
$X$ の第 $(i-K), (i-K+1), (i-K+2), \dots, (i-1)$ 項全てに $X_i$ を足す.

これを $i=N,N-1,\dots,K+1,K$ の順に行うと, $X$ は次のようになる.

$(S_1, S_2, \dots, S_{K-1}, S_0, \underbrace{0, 0, \dots, 0}_{N-K})$

(下) の仮定から, $S_0=S_1=\dots=S_{K-1}$ であるから, 最後に第 $1,2, \dots, K$ に対して, $-S_1$ を足すことで, 全ての項を $0$ にすることができた.

解法 (2) 判定

よって, 特徴づけにより, 求めるべきは $(A_l, \dots, A_r)$ において, $t=0,1, \dots, K-1$ に対して, 添字を $K$ で割った余りが $t$ であるような第 $t$ 項における総和が $t$ によらず一致するか? という問題に帰着された.

このとき, 第 $l$ 項から第 $r$ 項までに対して, 添字を $K$ で割った余りが $t$ であるような第 $t$ 項における総和 $S^{(t)}_{l,r}$ は $B^{(t)}$ を $j \equiv t \pmod{K}$ であるならば第 $j$ 項を $A_j$ そうでなければ $0$ であるような整数列とすると, $S^{(t)}_{l,r}:=B^{(t)}_l+\dots+B^{(t)}_r$ で求められる. これは累積和による前計算によって高速化できる.