UVa 10616 : Divisible Group Sums

問題リンク：http://uva.onlinejudge.org/external/106/10616.html

問題概要：
n個の要素からなる配列A[i](0<=i<=n-1)とQ個のクエリーが与えられる
配列A[i]からM個の要素を選んだ時、その和がDで割りきれるような選び方は何通り存在するか

クエリーは以下の形式からなる
D M
D,Mは上の説明に登場するものである

解法：
0-1Knapsack
dp[選んだものの総和をDで割った余り][何個選んだか] := 総数
ただし、配列A[i]の要素に負の値がくることもあるので注意
さらに、dp配列はunsigned long longにしないとオーバーフローする

コード：

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
#include<climits>
#include<cassert>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define LLINF (LLONG_MAX)
#define MAX 201
 
 
using namespace std;
 
typedef unsigned long long ll;
 
int N,Q,D,M;
int A[MAX];
ll dp[21][11];
 
 
int main()
{
  int CNT = 1;
  while(scanf("%d %d",&N,&Q),N|Q)
    {
      rep(i,N)
	{
	  scanf("%d",&A[i]);
	}

 
      printf("SET %d:\n",CNT++);
      rep(k,Q)
    {
      scanf("%d %d",&D,&M);
      printf("QUERY %d: ",k+1);
      rep(i,D+1)rep(j,M+1)dp[i][j] = 0;
      dp[0][0] = 1;

      rep(i,N)
        {
          for(int cnt=M-1;cnt>=0;cnt--)
	    {
	      rep(sum,D)
		{
		  if(cnt+1 <= M)
		    {
		      dp[abs(D+(sum+A[i])%D)%D][cnt+1] += dp[sum][cnt];
		    }
		}
	    }
        }
      printf("%lld\n",dp[0][M]);
    }
    }
  return 0;
}