よく眺めると解ける。

ratingがついに2000に乗りました。嬉しい。

C. Lieges of Legendre

問題

石山が$n$個与えられ、整数$k$が固定される。 2人のプレイヤーが交互に以下の操作のいずれかを行い、先に行えなくなった方の負け。

  • ある石山から石をひとつ取り除く。
  • ある石山で石の数が偶数$2n$のものを選びその石山を取り除き、石の数が$n$の石山を$k$個加える。

どちらが勝つか答えよ。

解法

grundy数を計算する。 同じ大きさの石山が偶数個あれば排他的論理和の性質から取り除けるので、$k$はその偶奇のみ見ればよい。

$k$が偶数の場合は周期性より$O(1)$。 $k$が奇数の場合は、$a_i$が奇数なら$0$、そうでなければ再帰して$O(\log n)$。 ただし、$0$に近い部分は特別に対処する。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
int mex(int a, int b) {
    for (int i = 0; ; ++ i) {
        if (i != a and i != b) {
            return i;
        }
    }
}
int grundy(int a, int k) {
    if (a == 0) return 0;
    if (k % 2 == 0) {
        if (a <= 2) return a;
        return (a+1) % 2;
    } else {
        if (a % 2 == 1) {
            if (a <= 3) return 1;
            return 0;
        }
        return mex(grundy(a-1,k), grundy(a/2,k));
    }
}
int main() {
    int n, k; cin >> n >> k;
    vector<ll> a(n); repeat (i,n) cin >> a[i];
    int result = 0;
    for (int it : a) result ^= grundy(it, k);
    cout << (result ? "Kevin" : "Nicky") << endl;
    return 0;
}