天天看点

hdu 5464 Clarke and problem (BestCoder Round #56 (div.2)) Clarke and problem

time limit: 2000/1000 ms (java/others)    memory limit: 65536/65536 k (java/others)

total submission(s): 350    accepted submission(s): 151

problem description

clarke is a patient with multiple personality disorder. one day, clarke turned into a student and read a book.

suddenly, a difficult problem appears: 

you are given a sequence of number a1,a2,...,an and

a number p.

count the number of the way to choose some of number(choose none of them is also a solution) from the sequence that sum of the numbers is a multiple of p(0 is

also count as a multiple of p).

since the answer is very large, you only need to output the answer modulo 109+7

input

the first line contains one integer t(1≤t≤10) -

the number of test cases. 

t test

cases follow. 

the first line contains two positive integers n,p(1≤n,p≤1000) 

the second line contains n integers a1,a2,...an(|ai|≤109).

output

for each testcase print a integer, the answer.

sample input

1

2 3

1 2

sample output

2

hint:

2 choice: choose none and choose all.

source

bestcoder round #56 (div.2)

翻译:

问题描述

输入描述

输出描述

输入样例

输出样例

解题思路:

官方提示:

设d(i, j)d(i,j)表示前ii个数,模pp为jj的方案数,则容易得到d(0,

0)=1, d(i, j)=d(i-1, j)+\sum_{j=0}^{p-1} d(i-1, (j-a[i]) \ mod \ p)d(0,0)=1,d(i,j)=d(i−1,j)+∑​j=0​p−1​​d(i−1,(j−a[i]) mod p),很多人没1a是因为没注意|a_i|

\le 10^9∣a​i​​∣≤10​9​​

个人认为这其实就是一个dp的题,因为以前做过这样类似的,所以1 a

哈哈,上代码:

继续阅读