Given a list of N numbers you will be allowed to choose any M of them. So you can choose in NCM 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.
题意：给你n个数，提出q的问题，问你从n个数取出m个求和能被d整除的有几个。
我们设一下dp[i][j][mod]表示取到第i个数，取了j位数余数为mod的方案数。显然我们可以得到递推公式,
dp[i][j][mod]+=dp[i-1][j][mod](这一位数不取）or dp[i][j][((mod+a[i])%d+d)%d]+=dp[i-1][j-1][mod]。
((mod+a[i])%d+d)%d这样取余是为了处理负数的出现。
#include <iostream>
#include <cstring>
using namespace std;
int a[220];
long long dp[220][30][30];
int main()
{
int t;
cin >> t;
int ans = 0;
while(t--) {
ans++;
int n , q;
cin >> n >> q;
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
cout << "Case " << ans << ":" << endl;
for(int i = 0 ; i < q ; i++) {
int d , m;
cin >> d >> m;
memset(dp , 0 , sizeof(dp));
for(int i = 0 ; i <= n ; i++) {
dp[i][0][0] = 1;
}
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= m ; j++) {
for(int l = 0 ; l < d ; l++) {
dp[i][j][l] += dp[i - 1][j][l];
dp[i][j][((l + a[i]) % d + d) % d] += dp[i - 1][j- 1][l];
}
}
}
cout << dp[n][m][0] << endl;
}
}
return 0;
}