思路与算法

用布尔数组dp[r]记录处理完前若干数后，带符号和模k可否为r。初始仅dp[0]为真。每读入a，转移到(r+a)%k及(r-a+k)%k，其中先令a%=k。最后检查余数0。

正确性说明

相同余数的整数与后续任何加减组合得到的余数都相同，因此只保留余数不丢失可行性。每个数的正负两种选择均被枚举，按已处理数个数归纳，数组恰好覆盖所有可达余数；余数0恰表示整除。

复杂度

初始化O(k)，处理N个数共O(Nk)，空间O(k)，含下一层数组。数值先取模，转移使用0..k-1内整数。

易错点

必须使用新数组，不能在同一层传播成重复使用一个数。负余数要规范化。0和负的整倍数都可整除；不能把目标限制为正数和。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<bool> d(k);
    d[0] = true;
    while (n--) {
        int a;
        cin >> a;
        a %= k;
        vector<bool> next(k);
        for (int r = 0; r < k; ++r)
            if (d[r])
                next[(r + a) % k] = next[(r - a + k) % k] = true;
        d.swap(next);
    }
    cout << (d[0] ? "YES" : "NO") << '\n';
}