← 返回题目列表

AtCoder · awc0042_d

D. 糖果分发

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

分数: 400 分

问题陈述

高桥有一个盒子,里面装有 N 糖果排成一排。的重量 i左边第一个糖果是 A_i 克。

高桥想从这个盒子里连续选择一颗或多颗糖果,把它们装进袋子里,然后把它们作为礼物送给他 K 朋友们。由于他想将糖果按重量平均分配给所有朋友,因此所选糖果的总重量必须是 K 克。

找出选择一种或多种连续糖果的方法数,使得所选糖果的总重量是以下的倍数 K。请注意,如果所选糖果的范围不同(即起始位置或结束位置不同),即使总重量相同,它们也会被视为不同的选择。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

N K
A_1 A_2 \ldots A_N
  • 第一行包含糖果的数量 N 和好友数量 K,用空格分隔。
  • 第二行包含每个糖果的重量 A_1, A_2, \ldots, A_N,用空格分隔。

输出

在一行中打印选择一种或多种连续糖果的方法数,使得所选糖果的总重量是以下的倍数 K.


示例输入 1

5 3
1 2 3 1 2

示例输出 1

7

示例输入 2

8 5
2 3 5 1 4 2 3 5

示例输出 2

16

示例输入 3

10 1000000000
500000000 500000000 300000000 700000000 100000000 900000000 400000000 600000000 200000000 800000000

示例输出 3

15