本文共 1887 字，大约阅读时间需要 6 分钟。

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 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        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
        
         #include 
         
          #include 
          
           #include 
           
            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
           
          
         
        
       
      
     
    
   

转载地址：http://zfmvi.baihongyu.com/