AtCoder Beginner Contest 146：E - Rem of Sum is Num

問題
解法
解答

問題

https://atcoder.jp/contests/abc146/tasks/abc146_e

解法

K = 1 のとき，答えは 0．

そうでないとき，各 A_i から 1 を引き，累積和を求めておくと，「A の空でなく，長さが K 未満である連続する部分列で，要素の和を K で割った余りが 0 になるものの数」を求める問題になる．これは，左端から map で各数字の登場回数をメモしておき，A_k と等しい値が A_(k - K) ~ A_(k - 1) の間にいくつ表れているかを答えに加算していくことで求められる．O(NlogK)．