Editorial for DMOPC '17 Contest 2 P5 - Game
Submitting an official solution before solving the problem yourself is a bannable offence.
Let ~Z=\max(X, Y)~.
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: ~\mathcal O(Z^3)~
For the second subtask, say that there are ~N~ stones currently. The first player can win if they are allowed to take ~A~ stones on this turn. Then clearly, the player can win if they are allowed to take ~B~ stones on this turn and ~B \ge A~. So store the least amount of stones the first player must take to guarantee a win if there are currently ~N~ stones and call this ~dp[N]~. A DP recurrence can be found involving this array: if ~M~ is the largest number (less than ~N~) such that ~dp[M]>N-M+K~, then ~dp[N]=N-M~. (Also, ~dp=\infty~.)
Time Complexity: ~\mathcal O(Z^2)~
For the third subtask, finding each ~dp[N]~ in the second subtask can be sped up. Previously, it took ~\mathcal O(N)~ to compute ~dp[N]~. Using data structures such as an RMQ segment tree, this may be sped up to ~\mathcal O(\log N)~.
Time Complexity: ~\mathcal O(Z \log Z)~
For the fourth subtask, first note the following fact: For any ~M~ with ~dp[M] \ne M~, let ~N~ be the largest number less than ~M~ such that ~dp[N]=N~. Then ~dp[M]=dp[M-N]~. This claim can be proved by strong induction on ~M-N~.
Consider an arbitrary ~N_1~ with ~dp[N_1]=N_1~ and ~N_1 \ge K+2~ (it is not hard to see that ~dp[N]=N~ for all ~1 \le N \le K+2~). Let ~N_3~ be the smallest number larger than or equal to ~N_1-K~ with ~dp[N_3]=N_3~ and ~N_2~ be defined as ~N_1+N_3~. Then ~N_2~ is the least number larger than ~N_1~ such that ~dp[N_2]=N_2~.
Proof: It can be seen from the earlier claim and from the fact that ~dp[N_2-N_1]=N_2-N_1~, that for any ~N~ with ~N_1<N<N_2~, that ~dp[N] \ne N~ and also ~dp[N]=dp[N-N_1] \le N_3-(N-N_1)+K=N_2-N+K~. Now for any ~N~ with ~0<N \le N_1~, ~dp[N] \le N = N-(N_1+N_1-K)+K \le N-(N_1+N_3)+K = N-N_2+K~. So the largest number ~M~ less than ~N_2~ such that ~dp[M]>N_2-M+K~ is ~0~. So ~dp[N_2]=N_2~.
So using this, all ~N~ such that ~dp[N]=N~ can be computed. There are approximately ~\log_2 Z~ such ~N~s between ~K+2~ and ~Z~. For each ~N~ with ~dp[N]=N~, compute the number of ~M~s such that ~dp[M]=1~ using the first claim. Then, using these values, the final answer can be computed using the first claim.
Time Complexity: ~\mathcal O(\log Z)~