# 題目: UVa 10616 - Divisible Group Sums

# 題目說明

給一個有N個數字的序列，取出M個數字相加，使結果能整除D，求總方法數

---

INPUT:
每筆測資第一行輸入兩個整數N、Q
接下來有N行，每行輸入一個整數
接下來有Q行，每行輸入兩個整數D、M
當N、Q為0時結束程式

---

OUTPUT:
輸出符合題目條件的總方法數

# 解題方法

需要先將輸入的N個數字(num[i])做處理

1. 若為正數，num2[i] = num[i] % D，直接取D的餘數
2. 若為負數，num2[i] = num[i] % D + D，取D的餘數後加D，使之變正數

定義一個dp[j][k]
j為當前取到的數值
k為取幾個數

轉移方程為dp[j][k] += dp[j - num2[f]][k - 1]
最後將所有dp[D的倍數][M]相加為答案

# 參考程式碼

#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N, Q, D, M;
	int a, cases = 0;
	long long dp[201][11];

	while (cin >> N >> Q, N && Q)
	{
		vector<int> num;
		while (N--) cin >> a, num.emplace_back(a);

		cout << "SET " << ++cases << ":\n";

		for (int i = 1; i <= Q; ++i)
		{
			cin >> D >> M;

			vector<int> num2;
			long long ans = 0;
			memset(dp, 0, sizeof(dp));

			for (auto& j : num) num2.emplace_back(j % D > 0 ? j % D : j % D + D);

			dp[0][0] = 1;
			for (int f = 0; f < num2.size(); ++f) for (int j = 200; j >= num2[f]; --j)
				for (int k = M; k > 0; --k) dp[j][k] += dp[j - num2[f]][k - 1];

			for (int j = 0; j <= 200; j += D) ans += dp[j][M];
			cout << "QUERY " << i << ": " << ans << "\n";
		}
	}

	return 0;
}

# 參考資料

https://blog.csdn.net/mobius_strip/article/details/41252307
https://summon528.github.io/2017/12/05/UVA-10616-Divisible-Group-Sums/