算法

(动态规划) $\mathcal{O}(nk)$

本题是经典的01可达性背包问题

记 dp[i][j] 表示前 $i$ 个数通过添加 + 或 - 是否能凑出 $j$

吐槽一句：这题连我都会，居然是绿题

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i] = (a[i]+k)%k;

    vector dp(n+1, vector<int>(k));
    dp[0][0] = 1;
    rep(i, n)rep(j, k) {
        dp[i+1][(j+a[i]+k)%k] |= dp[i][j];
        dp[i+1][(j-a[i]+k)%k] |= dp[i][j];
    }

    if (dp[n][0]) puts("Divisible");
    else puts("Not divisible");
}

int main() {
    int t;
    cin >> t;

    while (t--) solve();

    return 0;
}