ABC146-E(500) Rem of Sum is Num
概要
Nの長さを持つ数列がある。(N <= 2*10^5 , A_i <= 10^9)。K(1 <= 10^9)という数を用意する。Nの連続部分列で、総和をKであまりとったものが連続部分列の長さとなる組み合わせの数を答えよ。
ACするまで
1. 条件を満たす区間が連続しない連続部分列の数え上げ。しゃくとりの線ではない気がする。
2. とりあえず累積和をとる方向性で進める。
3. 連続部分列の長さという変動する要素があるので扱いづらい。これをどうにかして消去できないのかー＞全要素-1すればいい感じになりそう。
4. それで累積和を取ってみる。そこでS_i==S_jとなる(i, j)を数え上げる。ー＞サンプル２WA
5. 問題文をよく読むと、Kによる長さの制約が存在してる。
6. 修正ー＞AC
考察
連続部分列の数え上げについては、基本的に考えてるものとして、
1. 数え上げ対象の区間が、区間端を一つずらしても対象になってそうなら、しゃくとり法
2. そうでないのならば、転倒数の要領でBIT、連想配列とか
というのを経験から考えてる。
今回は後者の方なので、これで考える。
考える際にまず邪魔となるのが、区間の長さによる累積和区間での目標値である。(例えば、長さ3の連続部分列なら、区間和のあまりが3となるものを見る感じ)このままでは画一でどうしても扱いづらい。
ここで、個数という情報をどうにかして操作して、普遍的に累積和区間での目標値が一定になるようにしたい。この時、個数に関連するという点で、すべてのA_iに前処理として-1をすれば、「区間の和のあまりが区間の長さとなる」という条件は、「区間の和のあまりが0になる」となる。
区間の個数に依存する数が区間の和なので、すべての要素に等しく何かしらすればいいという発想から来ている。
この前処理をすることで、区間の和のあまりが0となる区間を探せばよいとわかる。あまりで考えるので、累積和自体も％Kしてよい。（ただし、累積和の区間を求める際の減算では、(s_i - s_j + K) % Kとして、マイナスに行かないようにする必要がある）
これに関しては、mapに左から見て、累積和配列Sにxがy個含まれてるのを M[x]=y; でメモしておき、今見てるのがS_iならば、 M[S_i] の個数だけ前にその数があったので、答えに加算すればよい。そして、今見てる数を同様にMに加算しておく(M[S_i]++)
ただし、問題文に書かれてる条件として、部分列の長さは最大でもKというのを忘れてはならない。つまり、今見てるS_iと同じと言えど、あまりにも前のものは部分列の長さが最大でKというのを満たさない。これに関しては、S_iを見る際に、例えば、iがK以上の長さとか(実装法で1前後ずれることあり)になったら、一番昔に相当するS_(i - K)を消す(M[S_(i - K)]--)、という方法で上記の実装に落とし込める。
具体的な実装はソースコードを参照
ACソースコード：
