|
|
|
|
描述 Description |
|
|
|
有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的值即可。
|
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
第一行有两个正整数，分别代表n和k。输入数据保证有n<=500 000，k<=100 000。
以下n行每行一个正整数。这些正整数保证都不大于10 000。
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
一个正整数。它应该是你的答案mod 1234567的结果。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
各个测试点1s
|
|
|
|
|
|
|
|
来源 Source |
|
|
|
Matrix67 根据经典问题改编
|
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1416 |
|
其它 |
通过 |
0人 |
提交 |
6次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
