HDU 5464 Clarke and problem(DP 01 백팩)

Clarke and problem
Time Limit 20001000 MS (JavaOthers)    Memory Limit 6553665536 K (JavaOthers)
Total Submission(s) 400    Accepted Submission(s) 179
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) 

/*01  DP*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string.h>
using namespace std;
const int N=1000+10;
const int mod=1e9+7;
int num[N];
int p,n;
int dp[N][N];
int main(){
	int t,i,j;
	scanf("%d",&t);
	while(t--){
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		scanf("%d%d",&n,&p);
		for(i=1;i<=n;i++){
			scanf("%d",&num[i]);
			num[i]%=p;
			//        ...                
			num[i]=(num[i]+p)%p;   
		}		  
	    for(i=1;i<=n;i++){   //           
	    	for(j=0;j<p;j++){   //     
	    	 //         j  i-1   j    
	    	   dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;   
			//             I-1       
			dp[i][(j+num[i])%p]=(dp[i][(j+num[i])%p]+dp[i-1][j])%mod;
			}
		}
		printf("%d
",dp[n][0]);
	}
    return 0;	
}





/*        */
/*
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
const int N=1000+10;
const int mod=1000000000+7;
int num[N];
int p,n;
int re;
void dfs(int now,int sum){
	int i;
	if(sum%p==0)
	  {
	  	re++;
	  	re%=mod;
	  	return;
	  }
	else if(sum>p||now>=n)
	 return;	
	dfs(now+1,sum+num[now]);
	dfs(now+1,sum);
}
int main(){
	int t,i;
	scanf("%d",&t);
	while(t--){
		re=1;
		scanf("%d%d",&n,&p);
		for(i=0;i<n;i++)
		  scanf("%d",&num[i]);
		sort(num,num+n);
		dfs(0,0);
		printf("%d
",re);
	}
    return 0;	
}
*/