https://beta.atcoder.jp/contests/abc105/tasks/abc105_d
考察過程
1. よくあるテクを使う
2. 「右側を固定して、条件を満たす左端を高速に数え上げる」
3. 区間和に関する問題なので、先頭からの累積和を使って条件を考える
4. [l,r]の区間和がMの倍数 ↔ [0,l)と[0,r]のそれぞれの累積和がmodMで等しい
5. mapを使ってこれまでの累積和modMの個数をカウントしておけば解ける
解法
https://beta.atcoder.jp/contests/abc105/submissions/2994810
「右側を固定して、条件を満たす左端を高速に数え上げる」テクを使う。
「[l,r]の区間和がMの倍数 ↔ [0,l)と[0,r]のそれぞれの累積和がmodMで等しい」ことが言える。
よって、rを固定した時に上の条件を満たすlを数え上げて総和を取ればいい。
「cnt[i] := 今までの累積和の中でmodMがiであるものの個数」を用意する。
あとは、累積和であるsmを使いながら答えを求めていく。
int N, M, A[101010]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, N) cin >> A[i]; map<int, int> cnt; cnt[0] = 1; ll ans = 0, sm = 0; rep(i, 0, N) { sm += A[i]; ans += cnt[sm%M]; cnt[sm%M]++; } cout << ans << endl; }