ABC105 D Candy Distribution

問題概要

数列が与えられる。その連続した区間を取り出すとき、その区間に含まれる数の和がMの倍数である区間はいくつあるか。

取った方針

連続した区間の和を高速に求める->累積和
累積和から区間[i,j]の和を計算する際はj番目の累積和 - i-1番目の累積和 を行う。
これがMで割った時あまりが0になればよい。
よって、累積和の数列をMで割ったあまりによって場合分けする。
Mで割ったあまりが同じ2数l,rを選択すれば、r-lは必ずMの倍数になる。
これを実装するにはあまりをキーとしたmapを用意すればよく、数列の長さNが10⁵なのであまりの数も高々10⁵個である。
よって、最悪10⁵個のmapへの挿入が発生するので、O(NlogN)で通る。

正しい方針(解説の方針)

同上

得られた知見

・区間の和->累積和
・Mの倍数->余りに着目
・厳しい制約(10⁹とか)->厳しくない制約(10⁵、10²とか)に着目

解くのに必要な要素

・累積和
・剰余

周辺調査によって得られた知見

なし