まず、 の値については、 で割ったあまりで考えても変わりません。
そうすると、以下のような問題に帰着されます。
この問題は、部分和問題を解くときに用いられる動的計画法とほとんど同じ手法で解くことができます。
テーブルの初期値や遷移が少し違うことに注意してください。
#include<bits/stdc++.h> using namespace std; int main(){ int n, k; cin >> n >> k; vector<int> a(n); for(int i = 0; i < n; i++){ cin >> a[i]; a[i] %= k; } vector<vector<bool>> dp(n + 1, vector<bool>(k, false)); for(int i = 0; i < n; i++){ dp[i+1][a[i]] = true; for(int j = 0; j < k; j++){ if(dp[i][j] == false){ continue; } int s = (j + a[i]) % k; dp[i+1][j] = true; dp[i+1][s] = true; } } if(dp[n][0]){ cout << "Yes" << endl; }else{ cout << "No" << endl; } }