概要

連続するお菓子の区間（連続部分列）を選んだとき、その総重量が \(K\) の倍数になる区間の個数を数えます。

考察

連続部分列の和は、累積和を使うと高速に扱えます。
累積和を \(S_i = A_1 + A_2 + \cdots + A_i\)（\(S_0=0\)）とすると、区間 \([l, r]\) の和は

• \(A_l + \cdots + A_r = S_r - S_{l-1}\)

です。これが \(K\) の倍数である条件は

• \(S_r - S_{l-1} \equiv 0 \pmod K\)
• つまり \(S_r \equiv S_{l-1} \pmod K\)

となります。
よって「累積和を \(K\) で割った余り」が同じ位置のペアの数を数えれば、答えになります。

---

素朴に全ての区間を調べると、区間は \(O(N^2)\) 個あり（最大で約 \(2\times 10^5\) のとき \(4\times 10^{10}\) 個）、時間制限内に終わりません（TLE）。

そこで、「今までに出てきた累積和の余り」の個数を管理しながら左から順に見ていくことで、1回の走査で数え上げます。

具体例

\(K=5\)、余り列が（\(S_i \bmod 5\)として）
\([S_0,S_1,S_2,S_3] \bmod 5 = [0, 2, 0, 2]\) だったとします。

• 余り \(0\) は 2 回出現 → 同じ余り同士の組は \(\binom{2}{2}=1\) 個
• 余り \(2\) も 2 回出現 → \(\binom{2}{2}=1\) 個

合計 2 個の区間和が \(5\) の倍数になります。
（実装では「今見ている余りと同じ余りが過去に何回あったか」を逐次加算する形で同じことをしています。）

アルゴリズム

1. 変数 \(s\) を「現在までの累積和の余り」\(s = S_i \bmod K\) とする（初期値 0）。
2. 辞書 cnt に「各余りがこれまでに何回出たか」を保持する。
   • 最初は \(S_0=0\) が1回出現しているので cnt[0]=1 とする。
3. 各 \(A_i\) を左から順に処理し、
   • \(s \leftarrow (s + A_i) \bmod K\)
   • 今の余り \(s\) と同じ余りが過去に cnt[s] 回あれば、その回数分だけ「条件を満たす区間」が増えるので ans += cnt[s]
   • その後 cnt[s] += 1 として出現回数を更新する
4. ans を出力する。

この方法で、「\(S_r \equiv S_{l-1} \pmod K\) となるペア」を重複なく数えられます。

計算量

• 時間計算量: \(O(N)\)（1回走査し、辞書操作も平均的に定数時間）
• 空間計算量: \(O(M)\)（出現した余りの種類数 \(M \le \min(N, K)\)。ただし \(K\) が大きいので配列ではなく辞書を使う）

実装のポイント

• cnt[0] = 1 を忘れると、「先頭から始まる区間（\(l=1\)）」を数え漏れます。

• \(K\) は最大 \(10^9\) なので、余りのカウントを配列（長さ \(K\)）で持つのは不可能です。defaultdict(int) のような辞書で管理します。

• 累積和はそのまま足すと巨大になるので、都度 % K を取って余りだけ管理します（Pythonならオーバーフローはしませんが、計算量・扱いやすさの面で有利です）。

  ソースコード

import sys
from collections import defaultdict

def main():
    input = sys.stdin.buffer.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    cnt = defaultdict(int)
    cnt[0] = 1
    s = 0
    ans = 0

    for x in A:
        s = (s + x) % K
        ans += cnt[s]
        cnt[s] += 1

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。