対決!!! 飲み比べ [yukicoder No.669]

https://yukicoder.me/problems/no/669

前提知識

• grundy数

解法

https://yukicoder.me/submissions/246557

対戦系でかつnimっぽさがあるので、grundy数を実験で計算して規則性を求めてみよう（関数exp）。
やってみると明らかで、iml残っているときのgrundy数はi%(K+1)となっている。
全てのお酒についてgrundy数を計算し、そのxor積が0なら"NO", そうでないなら"YES"とする。

int N, K, A[1010101];
//---------------------------------------------------------------------------------------------------
int dp[1010101];
void exp() {
    rep(i, 1, 50) {
        set<int> g;
        rep(j, max(0, i - K), i) g.insert(dp[j]);
        while (g.count(dp[i])) dp[i]++;
    }
    rep(i, 0, 50) printf("dp[%d] = %d\n", i, dp[i]);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];

    //exp();

    int g = 0;
    rep(i, 0, N) g ^= A[i] % (K + 1);
    if (g) printf("YES\n");
    else printf("NO\n");
}