ABC146. E. Rem of Sum is Num - phyllo’s algorithm note

長さNの正整数列A_iと正の整数Kが与えられる。
このとき、Aの空でない連続する部分列で、「要素の和のmod Kと要素数が等しくなるものの数」を求めよ。
ただし、位置が異なる場合は区別する。

問題を式で表現すると、

(Σ_{i=l}^{r} Ai) mod K = r - l + 1

と書ける。
ここで、左辺の和を累積和S_iに置き換えて考えると、

(S_{r} - S_{l-1}) mod K = r - (l - 1)

と変形でき、整理すると、

(S_{r} - r) mod K = (S_{l-1} - (l-1)) mod K

のようになる。
したがって、l < rで、r-l < Kであるような範囲で、「(S_i - i) mod K」が等しくなるような個数を数える問題になる。

X_i = (S_i - i) mod Kとすると、これは、各iについて、i+K-1までの範囲にあるjについて、X_iと等しいX_jの個数を求めることだが、これは、mapなどで、i+1に移動する際に、X_iを消してX_{i+1}を追加するような操作をすれば、高速に求められる。

全体で、O(NlogK)で高速に求められる。

以前の式変形する問題。