UVa-10616 : Divisible Group Sums
問題概要
長さN(<200)の数列が与えられる。その数列からM(<=10)個選んで和がD(<20)で割りきれる場合の数を求める問題。クエリ数(M,Dが与えられる)Q(<10)。
解法
余りの値といくつ使ったかを見ながらDP。オーバーフローや、値の重複に注意すること。
acceptされたコード
計算量O(Q*N^2*M*D)。ほんとはもう少し抑えられているかも(N^2が怪しい)。
#include <cstdio> #include <cstring> #include <map> using namespace std; typedef long long int64; const int MAX_N = 200; const int MAX_D = 20; const int MAX_M = 10; int N, Q, D, M; pair<int,int> as[MAX_N]; int64 dp[MAX_N+1][MAX_M+1][MAX_D]; bool init(){ scanf("%d%d", &N, &Q); map<int,int> dict; for(int i=0, x; i<N; i++){ scanf("%d", &x); dict[x]++; } N = 0; for(map<int,int>::iterator itr=dict.begin(); itr!=dict.end(); itr++){ as[N++] = make_pair(itr->first, itr->second); } return !(N==0 && Q==0); } int64 sub(){ memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1; for(int i=0; i<N; i++){ for(int j=0; j<=M; j++){ for(int d=0; d<D; d++){ for(int k=0; k<=as[i].second && j+k<=M; k++){ dp[i+1][j+k][((d+(int64)as[i].first*k)%D+D)%D] += dp[i][j][d]; } } } } return dp[N][M][0]; } void solve(){ for(int i=0; i<Q; i++){ scanf("%d%d", &D, &M); printf("QUERY %d: %lld\n", i+1, sub()); } } int main(){ int c = 1; while(init()){ printf("SET %d:\n", c++); solve(); } return 0; }