題目： 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;

// reference: https://ppt.cc/fAF1Zx

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;

    // 將所有數字轉換到 0 ~ D 區間
    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博客