Divisible Group Sums-白红宇

Divisible Group Sums

阅读量：4621 次

发布时间：2019-06-09

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

Divisible Group Sums

Given a list of N numbers you will be allowed to choose any M of them. So you can choose in ^NC_M ways. You will have to determine how many of these chosen groups have a sum, which is divisible by D.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

The first line of each case contains two integers N (0 < N ≤ 200) and Q (0 < Q ≤ 10). Here N indicates how many numbers are there and Q is the total number of queries. Each of the next N lines contains one 32 bit signed integer. The queries will have to be answered based on these N numbers. Each of the next Q lines contains two integers D (0 < D ≤ 20) and M (0 < M ≤ 10).

Output

For each case, print the case number in a line. Then for each query, print the number of desired groups in a single line.

Sample Input

10 2

5 1

5 2

5 1

6 2

Sample Output

Case 1:

Case 2:

分析：dp[i][j][k][t]表示前i个选了j个%k=t的方案数，转移一下即可；

　　　本质是一个01背包；

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               #include 
                
                 #include 
                 
                  #include 
                  
                   #define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector
                   
                    #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair
                    
                     #define sys system("pause")const int maxn=1e5+10;const int N=2e2+10;using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t,a[N],cas;ll dp[N][11][21][20];int main(){ int i,j; scanf("%d",&t); while(t--) { int q; memset(dp,0,sizeof(dp)); rep(i,1,20)dp[0][0][i][0]=1; scanf("%d%d",&n,&q); rep(i,1,n)scanf("%d",&a[i]); rep(i,1,n)rep(j,0,min(i,10))rep(k,1,20)rep(m,0,k-1) { dp[i][j][k][m]+=dp[i-1][j][k][m]; if(j)dp[i][j][k][m]+=dp[i-1][j-1][k][((m-a[i])%k+k)%k]; } printf("Case %d:\n",++cas); while(q--) { int b,c; scanf("%d%d",&b,&c); printf("%lld\n",dp[n][c][b][0]); } } return 0;}

转载于:https://www.cnblogs.com/dyzll/p/6534335.html

你可能感兴趣的文章