Chickes From Eggs

2 secs 1024 MB

dyktr_06

Problem

Submissions

Test cases

Editorial

まず、 $A$ の値については、 $K$ で割ったあまりで考えても変わりません。
そうすると、以下のような問題に帰着されます。

$1$ 個以上の卵を叩くとき、卵から出てきたひよこの数を $K$ で割った余りを $0$ にすることができるか？

この問題は、部分和問題を解くときに用いられる動的計画法とほとんど同じ手法で解くことができます。

テーブルの初期値や遷移が少し違うことに注意してください。

実装例(C++)

#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;
    }
}