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; }