#H. Candy Distribution

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Candy Distribution

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

有 nn 个盒子排成一排，其中左数第 ii 个盒子里面有 aia_i 个气球。你现在需要从一段连续的盒子当中取出所有的糖果，然后均匀地分给 mm 个小朋友。你希望最终每个小朋友手上的糖果数量相同，因此，你思考着有多少组连续的盒子里面的糖果数量是 mm 的倍数。形式化地说，你想找到一共有多少个二元组 (l,r)(l,r) 满足如下要求：

  • 1⩽l⩽r⩽n1\leqslant l\leqslant r\leqslant n。
  • ∑i=lrai∣m\sum\limits_{i=l}^r a_i\mid m。

数据范围：

  • 1⩽n⩽1051\leqslant n\leqslant 10^5，2⩽m⩽1092\leqslant m\leqslant 10^9。
  • 1⩽ai⩽1091\leqslant a_i\leqslant 10^9。

Translated by Eason_AC 2021.12.27

题目描述

N N 個の箱が左右一列に並んでおり、左から i i 番目の箱には Ai A_i 個のお菓子が入っています。

あなたは、連続したいくつかの箱からお菓子を取り出して M M 人の子供たちに均等に配りたいと考えています。

そこで、以下を満たす組 (l, r) (l,\ r) の総数を求めてください。

  • l, r l,\ r はともに整数であり 1 ≤ l ≤ r ≤ N 1\ \leq\ l\ \leq\ r\ \leq\ N を満たす
  • Al + Al+1 + ... + Ar A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r は M M の倍数である

输入格式

入力は以下の形式で標準入力から与えられる。

N N M M A1 A_1 A2 A_2 ... ... AN A_N

输出格式

条件を満たす組 (l, r) (l,\ r) の総数を出力せよ。

出力の際には、出力が 32 32 ビットの整数型に収まらない可能性があることに注意せよ。

样例 #1

样例输入 #1

3 2
4 1 5

样例输出 #1

3

样例 #2

样例输入 #2

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

样例输出 #2

6

样例 #3

样例输入 #3

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

样例输出 #3

25

提示

制約

  • 入力は全て整数である
  • 1 ≤ N ≤ 105 1\ \leq\ N\ \leq\ 10^5
  • 2 ≤ M ≤ 109 2\ \leq\ M\ \leq\ 10^9
  • 1 ≤ Ai ≤ 109 1\ \leq\ A_i\ \leq\ 10^9

Sample Explanation 1

各組 (l, r) (l,\ r) に対する和 Al + Al+1 + ... + Ar A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r は次のとおりであり、このうち 3 3 つが 2 2 の倍数です。 - (1, 1) (1,\ 1) に対する和: 4 4 - (1, 2) (1,\ 2) に対する和: 5 5 - (1, 3) (1,\ 3) に対する和: 10 10 - (2, 2) (2,\ 2) に対する和: 1 1 - (2, 3) (2,\ 3) に対する和: 6 6 - (3, 3) (3,\ 3) に対する和: 5 5

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 29ms
  • Powered by Hydro v4.9.27 Community