I have recently encounter this game-theory problem:

"Two player X and Y is going to play a game. Initially, they choose a number *P* (*P* ≤ 10^{18}) and a set of number *A*_{1}, *A*_{2}, *A*_{3}, ..., *A*_{n} (*n* ≤ 5000, 0 ≤ *A*_{i} < *P*). They will take their turns alternatively. In each turn, one player will remove a number from the set. After K turns, if the sum of all remaining numbers in the set is divisible by P, player X will win. Otherwise, player Y will win.

Determine who will win the game, if both of them play optimally. (The name of player who make the first move will be given in the input)"

I completely have no efficient approach for this problem (except the naive bitmask DP). Can anyone give me an hint? Thanks in advance.

I've just found it here: Shumen 2016.

I took a glance at the author's code and now my eyes hurt af. It'd be great if someone from Bulgaria could translate the solution.

A lot of cases (BTW two important conditions in the original problem not stated above, all

A_{i}are different and greater than 0):case 1: (N == K) X wins obviously

case 2: [K < N](K == 1) X wins iff there is a number in the input equal to the sum modulo P

case 3: [K < N, K > 1](K is even) Y wins as in its last move it has N — K + 1 different options (different modulo P as all

A_{i}<P) to choose from, and at least one of them must make the sum distinct from 0 modulo P.case 4: [K < N, K > 1, K is odd](N is even) Suppose we get to the moment when N — K + 2 numbers remain, so we have two moves left, one of Y and then one of X. Y must choose a number

A_{i}such that the current sum minusA_{i}is not equal to any other remainingA_{j}, and in that case he/she wins. Suppose it's impossible for Y, so for eachA_{i}there is anA_{j}(unique) such that (j≠i)A_{j}=sum-A_{i}. Observe this relation is symetric. But that's impossible, as allA_{i}must be different, and we have an odd number of different numbers modulo P left. So Y wins.case 5: [K < N, K > 1, K is odd, N is odd](numbers

A_{i}can be paired such that in each pair the sum is P, leaving only one number without pair) X wins by taking first the number without pair, and then after each move of Y, taking the other element in the corresponding pair.case 6: [K < N, K > 1, K is odd, N is odd](The numbers

A_{i}cannot be paired) Suppose we get to the moment when N — K + 2 numbers remain, so we have two moves left, one of Y and then one of X. Y can make sure easily that at this point at least two numbers cannot be paired with another such that the sum is P (in each move Y could take a number currently belonging to one such pair). Let's assume Y cannot win. This means that the numbers left, with sum S, in total N — K + 2, even, can be paired such that in each pair the sum is S. That means that S = S * (N — K + 2 ) / 2 mod P, that is, S = 0 mod P. But as we know, Y made sure at least two numbers could not be paired, so it's impossible to get to the losing state for him/her, so Y wins.Overall many cases, not very interesting to play at home :)