dp hdu 5464 Clarke and problem

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.

~开心，自己根据写出来的，还特别简洁。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#define ll __int64
#define mod 1000000007
using namespace std;
int dp[1005][1005],nums[1005];
int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,p;
        scanf("%d %d",&n,&p);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&nums[i]);
            nums[i] %= p;
            if(nums[i] < 0)
                nums[i] += p;
        }

        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j <= p; j++)
            {
                dp[i][j] = dp[i-1][j] + dp[i-1][(j-nums[i]+p)%p];
                dp[i][j] %= mod;
            }
        }
        printf("%d
",dp[n][0]);
    }
    return 0;
}