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