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