LightOJ1125 Divisible Group Sums（DP）

题目问从N个数中取出M个数，有多少种取法使它们的和能被D整除。

dp[i][j][k]表示，前i个数取出j个数模D的余数为k的方案数

我用“我为人人”的方式来转移，就从i到i+1转移，对于第i+1个数有取和不取两种选择，然后确定j和k这两个维度的情况。

另外题目说数字是32位有符号整数，所以是会出现负数的。。。模D之后加D再模D就行了。

#include<cstdio>
#include<cstring>
using namespace std;
long long dp[200][11][20];
int main(){
    int t,n,q,a[200],d,m;
    scanf("%d",&t);
    for(int cse=1; cse<=t; ++cse){
        scanf("%d%d",&n,&q);
        for(int i=0; i<n; ++i) scanf("%d",a+i);
        printf("Case %d:
",cse);
        while(q--){
            scanf("%d%d",&d,&m);
            memset(dp,0,sizeof(dp));
            dp[0][1][(a[0]%d+d)%d]=1;
            dp[0][0][0]=1;
            for(int i=0; i<n-1; ++i){
                for(int j=0; j<=m; ++j){
                    for(int k=0; k<d; ++k){
                        if(j<m) dp[i+1][j+1][((k+a[i+1])%d+d)%d]+=dp[i][j][k];
                        dp[i+1][j][k]+=dp[i][j][k];
                    }
                }
            }
            printf("%lld
",dp[n-1][m][0]);
        }
    }
    return 0;
}