lightoj1125_dp

http://lightoj.com/volume_showproblem.php?problem=1125

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

Output for Sample Input

10 2

5 1

5 2

5 1

6 2

Case 1:

Case 2:

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 int a[210], d[20], m[20];
17 LL dp[210][30][20];//dp[i][j][k]表示遍历2到第i个数，选了j个数，余数为k时的方案有多少
18 int main()
19 {
20     int t, n, q;
21     scanf("%d", &t);
22     for(int ca = 1; ca <= t; ca++)
23     {
24         scanf("%d %d", &n, &q);
25         for(int i = 1; i <= n; i++)
26             scanf("%d", &a[i]);
27         for(int i = 1; i <= q; i++)
28             scanf("%d %d", &d[i], &m[i]);
29         printf("Case %d:
", ca);    
30         for(int l = 1; l <= q; l++)
31         {
32             memset(dp, 0, sizeof(dp));
33             for(int i = 0; i <= n; i++)
34                 dp[i][0][0] = 1;
35             for(int i = 1; i <= n; i++)
36             {
37                 for(int j = 1; j <= m[l]; j++)
38                 {
39                     for(int k = 0; k < d[l]; k++)
40                     {
41                         dp[i][j][k] += dp[i-1][j][k];
42                         dp[i][j][((k+a[i])%d[l]+d[l])%d[l]] += dp[i-1][j-1][k];
43                     }
44                 }
45             }
46             printf("%lld
", dp[n][m[l]][0]);
47         }
48     }
49     return 0;
50 }