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

哈哈，上代碼：