数列の区間の和は，累積和によって表現するのが典型です．数列 \(A\) の（\(\mathrm{mod}\;M\)での）累積和を \(S_i = (A_1+A_2+\dots+A_i) \mathbin{\mathrm{mod}} M\) とします．すると，求める値は

\[ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right) = \sum_{1 \leq l \leq r \leq N} (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M \]

と書けます．ここで， \(S_0\coloneqq 0\) としました．

ここで， \(0 \leq S_{l-1},S_r < M\) であることを用いると，

\[ (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = S_r - S_{l-1} + \begin{cases} 0 & (S_{l-1} \leq S_r) \\ M & (S_{l-1} > S_r)\end{cases} \]

というふうに， \(\mathrm{mod}\) を含まない形で書けます．

\(X_r = \)（\(S_{l-1} > S_r\) である \(l=1,2,\dots,r\) の個数）と定義して，先程の変形を使うと，求める値は

\[ \sum_{r=1}^N \sum_{l=1}^r (S_r - S_{l-1}) \mathbin{\mathrm{mod}} M = \sum_{r=1}^N \left( S_r \times r - \sum_{l=1}^r S_{l-1} + M \times X_r \right) \]

と書けます． \(\sum_{l=1}^r S_{l-1}\) は \(S\) の累積和であり，簡単に求められます．あとは， \(X_r\) を各 \(r=1,2,\dots,N\) について高速に求められれば，答えを上の式で計算できます．

\(X_r\) は，Fenwick treeを用いて高速に計算できます．Fenwick tree は，数列 \(B=(B_1,B_2,\dots,B_M)\) に対して，以下の操作をどちらも \(O(\log M)\) 時間で行えるデータ構造です．

• \(i,x\) が与えられたとき，\(B_i \leftarrow B_i+x\) と更新する
• \(l,r\) が与えられたとき，\(B_l + B_{l+1} + \dots + B_r\) を計算する

ここで， \(B_x\) を「\(S_{l-1}=x\) となる \(l\) の個数」とすれば，\(X_r\) は次のアルゴリズムで計算できます．

• \(B_x = 0\) で初期化する
• \(r=0,1,\dots,N\) について以下を行う
  • \(X_r = B_{S_r + 1} + B_{S_r + 2} + \dots B_{M-1}\) を計算する
  • \(B_{S_r}\) に \(1\) を足す

Fenwick Tree は AtCoder Library で提供されているので，それを使うのが便利です．

全体の時間計算量は \(O(N\log M + M)\) です．

実装例 (Python)

from itertools import accumulate
from atcoder.fenwicktree import FenwickTree


N, M = map(int, input().split())
A = list(map(int, input().split()))
S = [0] + [x % M for x in accumulate(A)]
ft = FenwickTree(M)
s = 0
ans = 0
for r in range(N + 1):
    ans += S[r] * r - s + ft.sum(S[r] + 1, M) * M
    s += S[r]
    ft.add(S[r], 1)
print(ans)