分数: 475 点
问题陈述
给你一个序列 A = (A_1, A_2, \dots, A_N) of N 非负整数和正整数 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)。 \]
在这里, X \mathbin{\mathrm{mod}} M 表示非负整数时的余数 X 除以 M.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 4 2 5 0
示例输出 1
10
- A_1 \mathbin{\mathrm{mod}} M = 2
- (A_1+A_2) \mathbin{\mathrm{mod}} M = 3
- (A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3
- A_2 \mathbin{\mathrm{mod}} M = 1
- (A_2+A_3) \mathbin{\mathrm{mod}} M = 1
- A_3 \mathbin{\mathrm{mod}} M = 0
答案是这些值的总和, 10。请注意,外部总和未取模 M.
示例输入 2
10 100 320 578 244 604 145 839 156 857 556 400
示例输出 2
2736