连续数之和

连续数之和

测试数据来自 system/1090

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

有n个正整数排成一行。你的目的是要从中取出一个或连续的若干个数,使它们的和能够被k整除。

例如,有6个正整数,它们依次为1、2、6、3、7、4。若k=3,则你可以取出1、2、6,或者2、6、3、7,也可以仅仅取出一个6或者3使你所取的数之和能被3整除。当然,满足要求的取法不止以上这4种。事实上,一共有7种取法满足要求。

给定n和k,以及这n个数。你的任务就是确定,从这n个数中取出其中一个数或者若干连续的数使它们的和能被k整除有多少方法。

由于取法可能很多,因此你只需要输出它mod 1234567的值即可。

格式

输入格式

第一行有两个正整数,分别代表n和k。输入数据保证有n<=500 000,k<=100 000。

以下n行每行一个正整数。这些正整数保证都不大于10 000。

输出格式

一个正整数。它应该是你的答案mod 1234567的结果。

样例1

样例输入1

6 3
1
2
6
3
7
4

样例输出1

7

限制

各个测试点1s

来源

Matrix67 根据经典问题改编

娱乐赛(2)

未参加
状态
已结束
规则
OI
题目
104
开始于
2021-05-23 13:00
结束于
2021-05-23 16:00
持续时间
3.0 小时
主持人
参赛人数
1