abc 105 D - Candy Distribution (python)

連続する部分列→累積和を取る
累積和をとって、差を考える
余りの種類は m 個あるけど、数列の長さから高々 n 個に座圧できる。
基本テクの詰め合わせ。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

n,m = map(int,readline().split())
a = list(map(int,readline().split()))
c = [0]*(n+1)
for i in range(n):
  c[i+1] = a[i]+c[i]

d = defaultdict(int)
for i in c:
  d[i%m] += 1
  
ans = 0
for i in d.values():
  ans += (i-1)*i//2
print(ans)