## Editorial for DMOPC '17 Contest 2 P5 - Game

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: r3mark

Let .

For the first subtask, keep a 2-D boolean array storing if the first player can win given a certain state. The states are number of stones remaining and number of stones player is allowed to take on this turn. This array can be computed using DP.

Time Complexity:

For the second subtask, say that there are stones currently. The first player can win if they are allowed to take stones on this turn. Then clearly, the player can win if they are allowed to take stones on this turn and . So store the least amount of stones the first player must take to guarantee a win if there are currently stones and call this . A DP recurrence can be found involving this array: if is the largest number (less than ) such that , then . (Also, .)

Time Complexity:

For the third subtask, finding each in the second subtask can be sped up. Previously, it took to compute . Using data structures such as an RMQ segment tree, this may be sped up to .

Time Complexity:

For the fourth subtask, first note the following fact: For any with , let be the largest number less than such that . Then . This claim can be proved by strong induction on .

Consider an arbitrary with and (it is not hard to see that for all ). Let be the smallest number larger than or equal to with and be defined as . Then is the least number larger than such that .

Proof: It can be seen from the earlier claim and from the fact that , that for any with , that and also . Now for any with , . So the largest number less than such that is . So .

So using this, all such that can be computed. There are approximately such s between and . For each with , compute the number of s such that using the first claim. Then, using these values, the final answer can be computed using the first claim.

Time Complexity: