題目: UVa - 10616 - Divisible Group Sums
題目說明
給一些整數及一些 D
、M
,求在這些整數中,找 M
個相加可以被 D
整除的情況數。
Input: 每組測資前兩個整數依序為 N
、Q
,表有 N
個數字,及 Q
組 D
、M
,後面 N
行為 N
個整數,再後面 Q
行每行有兩個整數,依序代表 D
、M
。
Output: 輸出在這些整數中,找 M
個相加可以被 D
整除的情況數。
解題思路
為了方便計算,先對所有數字進行處理,使得數字都落在 0 ~ D
- 1 裡面,若是正數只要直接 % D
即可,負數需要特別處理,由於負數 % D
後範圍會落在 0 ~ - ( D
- 1 ),根據同餘定理,加上 D
後取餘的結果相同,因此加上 D
,使得所有數字都在範圍內。
定義 dp[k][j]
,表挑 j
個數字相加等於 k
的情況數。
之後遍歷處理好的陣列,核心想法為考慮目前遍歷的數字是否要加入,以此想法做 DP 即可。
由於 DP 縮減了一維,所以計算時要從後面往前算。
最後再將能被 D
整除的所有情況數相加即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| #include <bits/stdc++.h>
using namespace std;
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
int C; int N, Q; int D, M; int nums[201]; int tmp[201]; long long dp[201][11];
void init() { cin >> D >> M;
for (int i = 0; i < N; ++i) { tmp[i] = nums[i] % D; if (tmp[i] < 0) tmp[i] += D; }
memset(dp, 0, sizeof(dp)); }
void solve() { for (int i = 0; i < N; ++i) cin >> nums[i];
cout << "SET " << ++C << ":\n";
int q = 0; while (q < Q) { init();
dp[0][0] = 1; for (int i = 0; i < N; ++i) for (int j = M; j > 0; --j) { for (int k = tmp[i]; k <= 200; ++k) dp[k][j] += dp[k - tmp[i]][j - 1]; }
long long cnt = 0; for (int i = 0; i <= 200; i += D) cnt += dp[i][M];
cout << "QUERY " << ++q << ": " << cnt << '\n'; } }
int main() { while (cin >> N >> Q && N && Q) solve(); }
|
參考資料
UVa 10616 - Divisible Group Sums_小白菜又菜-CSDN博客