算法
(动态规划) $\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;
}