Lieges of Legendre
Contest: Codeforces Round 334 (Div. 1)
Difficulty rating: 2200
Tags: games, math

Kevin and Nicky Sun have invented a new game called Lieges of Legendre. In this game, two players take turns modifying the game state with Kevin moving first. Initially, the game is set up so that there are n piles of cows, with the i-th pile containing ai cows. During each player's turn, that player calls upon the power of Sunlight, and uses it to either:

1. Remove a single cow from a chosen non-empty pile.
2. Choose a pile of cows with even size 2·x (x > 0), and replace it with k piles of x cows each.

The player who removes the last cow wins. Given n, k, and a sequence a1, a2, ..., an, help Kevin and Nicky find the winner, given that both sides play in optimal way.

Input format:
The first line of the input contains two space-separated integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

The second line contains n integers, a1, a2, ... an (1 ≤ ai ≤ 109) describing the initial state of the game.

Output format:
Output the name of the winning player, either "Kevin" or "Nicky" (without quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the second sample, Nicky can win in the following way: Kevin moves first and is forced to remove a cow, so the pile contains two cows after his move. Next, Nicky replaces this pile of size 2 with two piles of size 1. So the game state is now two piles of size 1. Kevin then removes one of the remaining cows and Nicky wins by removing the other.

Example input:
2 1
3 4

Example output:
Kevin

Example input:
1 2
3

Example output:
Nicky

Editorial:
We'll use the concepts of Grundy numbers and Sprague-Grundy's Theorem in this solution. The idea is that every game state can be assigned an integer number, and if there are many piles of a game, then the value assigned to that total game state is the xor of the values of each pile individually. The Grundy number of a state is the minimum number that is not achieved among any state that the state can move to.
Given this brief intro (which you can read more about many places), we have to separate the problem into 2 cases, k even and odd. Let f(n) denote the Grundy number of a pile of size n. By definition f(0) = 0.
If k is even, then when you split the pile of size 2n into k piles of size n, the resulting Grundy number of that state is $$$$ as k is even. Given this, it is easy to compute that f(0) = 0, f(1) = 1, f(2) = 2, f(3) = 0, f(4) = 1. Now I will show by induction that for n ≥ 2, f(2n - 1) = 0, f(2n) = 1. The base cases are clear. For f(2n - 1), the only state that can be moved to from here is that with 2n - 2 cows. By induction, f(2n - 2) = 1 > 0,  so f(2n - 1) = 0. On the other hand, for 2n, removing one stone gets to a state with 2n - 1 stones, with Grundy number f(2n - 1) = 0 by induction. Using the second operation gives a Grundy number of 0 as explained above, so the smallest positive integer not achieveable is 1, so f(2n) = 1.
The case where k is odd is similar but requires more work. Let's look at the splitting operation first. This time, from a pile of size 2n we can move to k piles of size n, with Grundy number $$\underbrace{f(n) \oplus f(n) \oplus \cdots \oplus f(n)}_{k \text{ times}} = f(n),$$ as k is odd. So from 2n we can achieve the Grundy numbers f(2n - 1) and f(n). Using this discussion, we can easily compute the first few Grundy numbers. f(0) = 0, f(1) = 1, f(2) = 0, f(3) = 1, f(4) = 2, f(5) = 0. I'll prove that for n ≥ 2, f(2n) > 0, f(2n + 1) = 0 by induction. The base cases are clear. Now, for n ≥ 3, since a pile of size 2n + 1 can only move to a pile of size 2n, which by induction has Grundy number f(2n) > 0, f(2n + 1) = 0. Similarly, because from a pile of size 2n, you can move to a pile of size 2n - 1, which has Grundy number f(2n - 1) = 0, f(2n) > 0. Now computing the general Grundy number f(n) for any n is easy. If n ≤ 4, we have them precomputed. If n is odd and n > 4, f(n) = 0. In n is even and n ≥ 6, then f(n) is the minimal excludent of f(n - 1) = 0 and f(n / 2) (because n - 1 is odd and  ≥ 5, so f(n - 1) = 0.) We can do this recursively,
The compiexity is O(n) in the k even case and $${\mathcal {O}}(n\log MAX)$$ in the k odd case.