← 返回题目列表

AtCoder · abc378_e

H. 模西格玛问题

中文机器翻译题面 查看原题

分数: 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