ABC 105

https://atcoder.jp/contests/abc105

A. AtCoder Crackers

https://atcoder.jp/contests/abc105/tasks/abc105_a

B. Cakes and Donuts

https://atcoder.jp/contests/abc105/tasks/abc105_b

C. Base -2 Number

https://atcoder.jp/contests/abc105/tasks/abc105_c

D. Candy Distribution

https://atcoder.jp/contests/abc105/tasks/abc105_d

2026/1/22 あまりでまとめる系の問題だということを知った状態で自力 AC

https://kenkoooo.com/atcoder/#/contest/show/bd593eb7-d83c-479e-a99d-d6242eff88ea?activeTab=Problems

$S_0 = 0$, $S_x = \sum_{i=1}^{x} A_i$ とおくと

\begin{align*} A_l + \cdots + A_r \equiv 0 &\mod M \\ S_r - S_{l-1} \equiv 0 &\mod M \\ S_r \equiv S_{l-1} &\mod M \end{align*}

であるので累積和の $\mod M$ が同じものの組を数え上げれば良い。 $S_x \equiv r \mod M$, ($r \in [0, M)$) としたとき、$r$ に属するものが $k$ 個あるとすると、これらの中から 2 個選ぶ組み合わせの数 $\binom{k}{2} = k * (k-1) / 2$ を答えに加えれば良い。 $A_i \equiv 0 \mod M$ の場合はそれ単独で $M$ の倍数となるので、$S_0 = 0$ も分も個数に加えておくことで場合分けをせずに済む。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll A(N);
    rep(i, N) cin >> A[i];

    vll cm(N + 1);
    rep(i, N) {
        cm[i + 1] = cm[i] + A[i];
        cm[i + 1] %= M;
    }

    map<ll, ll> mp;
    rep(i, N) mp[cm[i + 1]]++;
    mp[0]++;

    ll ans = 0;
    for (auto [k, v] : mp) {
        ans += v * (v - 1) / 2;
    }
    cout << ans << endl;
}