Candy Distribution [AtCoder Beginner Contest 105 D]

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;
}