Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author: seanyang
For background information on the combinatorial game theory needed to solve this problem, please review my slideshow here or read this codeforces blog!
Hint 1
Find a function which finds the nimber of any state \(n_i, k_i\) in \(O(1)\) time.
Hint 2
It can be shown that the nimber of any pile \(n_i, k_i\) is precisely \((n_i - 1) \text{ mod } (k_i + 1)\).
Hint 3
Take the nimber sum of every pile \(n_i, k_i\).
Solution
Our goal is to find the nimber (also called a grundy number) of the overall state. If the grundy number is \(0\), the state is losing. Otherwise, the state is winning. We want to find the nimber of each pile and take the nimber sum of every pile.
The nimber of any pile \(i\) is \((n_i - 1) \text{ mod } (k_i + 1)\). To take the nimber sum of two piles, we take the bitwise XOR of both nimbers. Since XOR is a commutative operation, calculate the nimber of each pile, and keep a running XOR sum.
Time complexity: \(O(P)\)
Comments