Impartial Combinatorial Games

In a normal-play impartial combinatorial game:

1. A state with no successor is a losing state $\mathcal P$;
2. A state is a winning state $\mathcal N$ if and only if at least one of its successors is a losing state $\mathcal P$;
3. A state is a losing state $\mathcal P$ if and only if all of its successors are winning states $\mathcal N$.

For the first statement, if the player has no legal action, that player has already lost the game.

For the second statement, if a state has at least one losing successor, the player can move to that losing state. The opponent then faces a first-player-losing state, so the player eventually wins.

For the third statement, if no successor is losing, every move reaches a winning state. The opponent then faces a first-player-winning state, so the player eventually loses.

In Nim, the state $(a_1,a_2,\cdots,a_n)$ is a losing state $\mathcal P$ if and only if the Nim sum

Apply induction to all possible states:

1. If $a_i=0$ for every $i=1,\cdots,n$, the state has no successor and its Nim sum is $0$, so the statement holds.

2. Suppose $k = a_1\oplus a_2\oplus\cdots\oplus a_n\neq 0$. We must prove that the state is winning. In other words, we must construct a legal move whose successor is losing. By the induction hypothesis, it suffices to show that the successor satisfies $a'_1\oplus a'_2\oplus\cdots\oplus a'_n=0$. By the properties of the Nim sum (that is, XOR), this is equivalent to finding a pile of size $a_i$ from which some stones can be removed so that its new size is $a_i\oplus k$, or equivalently, $a_i>a_i\oplus k$.

   Let the highest bit of $k$ whose value is $1$ be bit $d$. Then there must be some $a_i$ whose bit $d$ is $1$. For the corresponding pile, we have $a_i>a_i\oplus k$, because in $a_i\oplus k$, bit $d$ is $0$, while all higher bits are the same as in $a_i$.

3. Suppose $a_1\oplus a_2\oplus\cdots\oplus a_n= 0$. We must prove that the state is losing. By the induction hypothesis, it is enough to prove that the Nim sum of every successor is not $0$. This is immediate: every legal move changes $a_i$ to $a'_i\neq a_i$, so the Nim sum becomes $a'_i\oplus a_i\neq 0$.

For games $G$ and $H$, their sum (or combined game) is denoted by $G+H$ and is the game

For a game $G$ and any losing game $A\in\mathcal P$, we have $G\approx G + A$.

For every game $H$, it suffices to prove that $G+H\approx G+A+H$.

If $G+H$ has a winning strategy, then $G+A+H$ also has one. If the opponent moves in subgame $A$, make a move that restores it to a losing state; otherwise, follow the winning strategy in $G+H$. This guarantees victory.

If $G+H$ is losing, then $G+A+H$ is also losing. Regardless of whether the move is made in subgame $G+H$ or subgame $A$, the opponent can restore the relevant subgame to a losing state on the next turn. Therefore, the first player cannot win.

Games $G$ and $G'$ are equivalent if and only if $G+G'\in\mathcal P$ is a losing game.

If games $G$ and $G'$ are equivalent, then $G+G'$ and $G+G$ are either both winning or both losing, while $G+G$ is losing. Indeed, after any move by the first player, the second player can make the same move in the other subgame, so the first player eventually has no move.

Conversely, if $G+G'$ is losing, Lemma 1 gives $G\approx G+(G+G') = (G+G)+G' \approx G'$.

For every finite impartial game $G$, there exists $n\in\mathbf N$ such that $G\approx *n$.

We prove the theorem by mathematical induction. Let $G = \{G_1,G_2,\cdots,G_k\}$. By the induction hypothesis, there are $n_1,n_2,\cdots,n_k$ such that $G_i\approx *n_i$. Consider the game

We will prove that $G'\approx *m$, where $m=\operatorname{mex}\{n_1,n_2,\cdots,n_k\}$ is the smallest natural number not in the set.

First, we show that $G\approx G'$. By Lemma 2, it suffices to prove that $G+G'$ is losing. Assume without loss of generality that $G\neq *0$. If the first player chooses $G_i$, the second player chooses $*n_i$; conversely, if the first player chooses $*n_i$, the second player chooses $G_i$. After these two moves, the game becomes $G_i+*n_i$, which is losing by Lemma 2 and $G_i\approx *n_i$. Hence $G\approx G'$.

Second, we show that $G'\approx*m$. By Lemma 2, it suffices to prove that $G'+*m$ is losing. Assume without loss of generality that $G'\neq *0$. If the first player chooses $*n_i\in *m$, then by the definition of $m$, the second player can choose $*n_i\in G'$, leaving the position $*n_i + *n_i\in\mathcal P$, so the first player loses. If the first player chooses $*n_i\in G'$ with $n_i<m$, the second player can choose $*n_i\in *m$, again leaving $*n_i+*n_i\in\mathcal P$, so the first player loses. Finally, if the first player chooses $*n_i\in G'$ with $n_i>m$, the second player can choose $*m\in *n_i$, leaving $*m+*m\in\mathcal P$, so the first player loses. This proves $G'\approx *m$.

By transitivity of equivalence, $G\approx *m$. This completes the induction and proves that every game $G$ is equivalent to a single-pile Nim game.

For an impartial game $G$, a state $x$ in it has Sprague–Grundy value $\operatorname{SG}(x)$ satisfies

Here, $\operatorname{mex}(A):=\min\{n\in\mathbf N:n\notin A\}$ is the smallest natural number not appearing in set $A$.

For an impartial game $G$, a state $x$ is winning for the first player if and only if $\operatorname{SG}(x)\neq 0$.

For impartial games $G_1,G_2,\cdots,G_n$,

Since $*a_1+ *a_2 + \cdots + *a_n$ is the Nim game with pile sizes $(a_1,a_2,\cdots,a_n)$, the result for Nim shows that the game

is losing for the first player. By Lemma 2, we have

Therefore,

Set $a_i=\operatorname{SG}(G_i)$. Then $G_i\approx *a_i$, and the algebraic properties of $\approx$ give

Hence,

The first player loses if and only if $n\equiv 0\pmod {k+1}$.

When $n\not\equiv 0\pmod {k+1}$, removing $n\bmod{(k+1)}\in[1,k]$ stones leaves the opponent in a losing state. Thus, the current state is winning for the first player.

Conversely, when $n\equiv 0\pmod {k+1}$, there is either no move, or after the first player removes $k'$ stones, the opponent can immediately remove $k+1-k'$ stones and return the game to a losing state.

As an application of the Sprague–Grundy theorem, let $f(n)$ be the SG value of the position with $n$ stones remaining.

For $n\le k$, induction gives $f(n)=n$. This is the same as a single-pile Nim game because the limit on the number of stones removed is not active. For $n>k$, we can prove that $f(n)=n\bmod{(k+1)}$, and hence

These values contain every residue modulo $k+1$ except $n\bmod{(k+1)}$. Therefore, $f(n) = n\bmod{(k+1)}$.

Write the size of each pile in binary. For every bit position $d$, count the number of piles whose size has bit $d$ equal to $1$, and take that count modulo $(k+1)$. If the remainder is $0$ at every bit position, the first player loses; otherwise, the first player wins.

The proof is analogous to the proof for Nim. Let $d$ be the highest binary bit whose remainder is not $0$, and let the corresponding remainder be $k'\le k$. The winning strategy is to choose, among the piles whose bit $d$ is $1$, $k$ piles and remove carefully chosen numbers of stones so that every bit-position remainder in the resulting position is $0$. The only point requiring explanation is why the final choices of removed amounts are always possible.

In fact, after choosing the $k'$ piles, removing $2^d$ stones from each makes the remainder at bit $d$ equal to $0$. For lower bit positions, the remainders can be distributed arbitrarily among the chosen piles.

The first player loses if and only if the Nim sum of the odd-indexed pile sizes, $a_1\oplus a_3\oplus\cdots\oplus a_{n-1+(n\bmod 2)}=0$.

Whenever a player moves stones from an even-indexed pile to an odd-indexed pile, the opponent can continue moving those stones to the next even-indexed pile (or remove them), so this move does not affect the odd-indexed-pile position. Each odd-indexed pile can then be viewed as an independent single-pile Nim game whose stones move down to the adjacent even-indexed pile (or are removed). By the Sprague–Grundy theorem for game sums, the SG value of Staircase Nim is the Nim sum of the SG values of these subgames. This gives the stated result.

At the start of the game, the first player loses if and only if the number of stones $n$ is a Fibonacci number.

Let $q$ be the quota, the maximum number of stones that may be removed in the current position. On the first turn, $q=n-1$; thereafter, $q$ is twice the number of stones removed on the previous turn. Consider the Fibonacci representation of the remaining number of stones $n$, namely, the unique decomposition of $n$ into a sum of positive, nonconsecutive Fibonacci numbers. We prove that the current state is winning if and only if $q$ is at least the smallest Fibonacci number in the decomposition of $n$.

The winning strategy is to remove all remaining stones if possible; otherwise, remove the smallest Fibonacci number in the decomposition. Since the next-smallest Fibonacci number in the decomposition is strictly greater than twice the smallest one, whenever a winning player cannot remove all the stones, the opponent cannot remove that next-smallest Fibonacci number on the following turn (which becomes the smallest Fibonacci number then), and therefore faces a losing state.

Conversely, suppose the current state is losing, and let the number removed on the current turn be $k$. It is strictly smaller than the smallest Fibonacci number $F$ in the current decomposition. If $F'$ is the smallest Fibonacci number in the next position, it is also the smallest Fibonacci number in the decomposition of $F - k$. Write $F'=F''+F'''$ with $F''>F'''$, that is, $F''',F'',F'$ are three consecutive Fibonacci numbers. If $k<F''$, adding $k + (F-k)$ in Fibonacci representation requires no carry and therefore cannot produce $F$. Thus, $k\ge F''$. Hence, the next-turn quota $2k>F''+F'''=F'$ is a winning state.

Assume without loss of generality that $a_1\le a_2$. Then the first player loses if and only if $a_1 = \lfloor(a_2-a_1)\phi\rfloor$, where $\phi=(\sqrt{5}+1)/2$ is the golden ratio.

Let $r,s > 1$ be irrational numbers satisfying $\dfrac{1}{r}+\dfrac{1}{s}=1$. Then the sequences $\mathcal B_r$ and $\mathcal B_s$ form a partition of the positive integers $\mathbf N_+$. They are then called complementary Beatty sequences.

Let $\mathcal A_r=\{kr:k\in\mathbf N_+\}$. Sort the elements of $\mathcal A=\mathcal A_r\cup\mathcal A_\ell$ into a sequence $\{a_i\}_{i\in\mathbf N_+}$. It suffices to prove that $i=\lfloor a_i\rfloor$ for every $i\in\mathbf N_+$; this gives that $\mathcal B_r\cup\mathcal B_s$ is a partition of the positive integers $\mathbf N_+$.

First, prove that no element is repeated in the sequence. Otherwise, there would be $k,\ell\in\mathbf N_+$ with $kr=\ell s$. Then

The left side is rational, while the right side is irrational, a contradiction. Thus, all numbers in the sequence are distinct.

Next, prove that the number of elements of $\mathcal A$ not exceeding $a_i$ is exactly $\lfloor a_i\rfloor$. Assume without loss of generality that $a_i\in\mathcal A_r$, so $a_i=kr$. Counting the elements of $\mathcal A_r$ and $\mathcal A_\ell$ separately, the number of positive integers not exceeding $a_i$ is

Thus, since $\{a_i\}$ is strictly increasing, the number of values not exceeding $a_i$ is exactly $i$. Therefore, $i=\lfloor a_i\rfloor$.

For every state with $a_1 < a_2$ that is losing, write it as $(a_1,a_2)$ and let $k = a_2 - a_1 \in\mathbf N_+$. Then $a_1=\lfloor k\phi\rfloor$ and $a_2=\lfloor k(\phi+1)\rfloor$. Since $\phi$ is the golden ratio, $\dfrac{1}{\phi}+\dfrac{1}{\phi+1}=1$. Rayleigh's theorem shows that the sequences $\{\lfloor k\phi\rfloor\}$ and $\lfloor k(\phi+1)\rfloor$ form a partition of the positive integers $\mathbf N_+$. This means that among all losing states with $a_1 < a_2$, written $(a_1,a_2)$, the components $a_1$ and $a_2$ each take every positive integer exactly once, and their difference $a_2-a_1$ also takes every positive integer exactly once.

A legal move in Wythoff's game either keeps one component fixed or keeps the difference fixed. Therefore, no legal move from a losing state can reach another losing state. Conversely, consider any winning state $(a_1,a_2)$ and assume without loss of generality that $a_1\le a_2$, with $k=a_2-a_1$. If $a_1>\lfloor k\phi\rfloor$, the first player can remove $(a_1 - \lfloor k\phi\rfloor)$ stones from each pile and reach a losing position. Conversely, by the preceding paragraph, for this value of $a_1$, there is a unique losing state $(a_1,a_2')$. If $a_1 > a_2'$, then clearly $a_2' < a_2$; otherwise, if $a_1 < a_2'$, choose $k'=a_2'-a_1$ so that $a_1=\lfloor k'\phi\rfloor$. Since $a_1 < \lfloor k\phi\rfloor$, we have $k' < k$, and therefore $a_2'=a_1 + k' < a_1+k = a_2$. Thus, whenever $a_1 < \lfloor k\phi\rfloor$, we have $a_2' < a_2$, and the first player can remove $(a_2-a'_2)$ stones from the second pile to reach a losing state.

For a coin-turning game $(S,f)$ and a position $G$, let $H(G)\subseteq S$ be the set of locations of the heads-up coins. Then the SG value of $G$ is

Consider a related game: in a position $G'$, several stones may be placed at each element of $S$. On each move, a player may remove one stone at $s$, choose a set $T\in f(s)$, and place one stone at every element of $T\setminus\{s\}$. For this game, define the basic position $G'_s$ as the position with one stone only at $s$. Every position in this game is the sum of the basic positions corresponding to all its stones. Indeed, when a new stone is placed, associate it with the stone that was removed. Then every stone arising during the game can be associated with one of the stones in the initial position, and the subgames corresponding to distinct initial stones do not interfere with one another. The entire game is therefore their sum. Since stones at the same location have the same basic-position SG value, the XOR property shows that the SG value of $G'$ depends only on the parity of the number of stones in each pile, not on their exact counts. Thus, for the position $G'$, let the set of positions with an odd number of stones be $H(G')$; this analysis gives

It remains only to establish the equivalence of $G'$ and $G$.

For a position $G'$ of the new game and a position $G$ of the coin-turning game, if the locations with an odd number of stones in $G'$ are exactly the locations of the heads-up coins in $G$, then $G'$ and $G$ are equivalent. By Lemma 2 of the Sprague–Grundy theorem, this is equivalent to proving that $G+G'$ is losing. The second player has a simple winning strategy: if the first player removes a stone at $s$ and there is more than one stone there, the second player directly imitates the move; otherwise, the second player chooses the same $s$ and $T\in f(s)$ as the first player, but acts in the other subgame: if the first player removes a stone, the second player flips coins, and if the first player flips coins, the second player removes stones. Whatever the first player does, the second player can continue responding while preserving the condition that the positions with an odd number of stones coincide with the heads-up coins. Thus the game must end when the first player has no legal move, so the first player loses. This proves the theorem.

The first player wins if and only if vertex $v$ is an essential vertex of graph $G$'s maximum matching; that is, in every maximum matching of graph $G$, vertex $v$ is matched.

First suppose that vertex $v$ is an essential vertex of a maximum matching of $G$. Let $G$ have a maximum matching $M$. The first player can move to the vertex in $M$ matched with vertex $v$, namely $u$. Since $v$ appears in every maximum matching of $G$, the size of a maximum matching of the residual graph $G'$ is at most $|M|-1$. After removing $M$'s edge $(v,v)$, we obtain in $G'$ a matching of size $|M|-1$, denoted $M'$; together these two facts show that $M'$ is a maximum matching of $G'$. In the position faced by the second player, vertex $u$ is not matched by $M'$. Therefore, the second player is in a losing state.

Conversely, suppose there is a maximum matching $M$ in which $v$ is unmatched. Since $M$ is maximum, every vertex adjacent to $v$ must be matched; otherwise, adding the edge between them to $M$ would produce a larger matching. Therefore, regardless of the first player’s choice, the second player is in a winning state.

In misère Nim, the state $(a_1,a_2,\cdots,a_n)$ is losing $\mathcal P$ if and only if either

1. Some $i$ satisfies $a_i>1$ and the Nim sum $a_1\oplus a_2\oplus\cdots\oplus a_n=0$, or
2. For every $i$, we have $a_i\le 1$, and the number of nonempty piles is odd.

Since having no legal move is a winning state $\mathcal N$, induction shows that when every pile contains only one stone, an odd number of piles corresponds to a first-player-losing state $\mathcal N$, while an even number of piles corresponds to a first-player-winning state $\mathcal N$.

Next, consider positions in which some piles contain strictly more than $1$ stone.

Case A: If only one pile contains more than $1$ stone, then the Nim sum is necessarily not $0$. Moreover, the first player can move to a position in which every pile contains at most $1$ stone and can control the parity of the number of nonempty piles. Thus, this is a first-player-winning state $\mathcal N$.

Case B: Now suppose more than one pile contains more than $1$ stone. Whatever move is made, the next position still has at least one pile containing more than $1$ stone. By the induction hypothesis, a first-player-losing next position corresponds to a zero Nim sum, while a first-player-winning next position corresponds to a nonzero Nim sum. This is exactly the same induction hypothesis as in normal Nim. Repeating the argument for Nim shows that the current position also follows the rule that a zero Nim sum corresponds to a first-player-losing state.

The games for different groups of piles are clearly independent. Therefore, it suffices to compute the SG value of each group, then compute the SG value of the whole game and determine whether it is winning. The key is how to compute the SG value of one group. This is not easy. A common approach to game-theoretic problems of this kind is to generate a table. Let the two piles in a group contain $(i,j)$ stones, respectively, and let the SG value be $f(i,j)$. A brute-force table-generating program gives the following result:

0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 4 
1 1 2 2 1 1 3 3 1 1 2 2 1 1 4 4
0 2 0 2 0 3 0 3 0 2 0 2 0 4 0 4
2 2 2 2 3 3 3 3 2 2 2 2 4 4 4 4
0 1 0 3 0 1 0 3 0 1 0 4 0 1 0 4
1 1 3 3 1 1 3 3 1 1 4 4 1 1 4 4
0 3 0 3 0 3 0 3 0 4 0 4 0 4 0 4
3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4
0 1 0 2 0 1 0 4 0 1 0 2 0 1 0 4
1 1 2 2 1 1 4 4 1 1 2 2 1 1 4 4
0 2 0 2 0 4 0 4 0 2 0 2 0 4 0 4
2 2 2 2 4 4 4 4 2 2 2 2 4 4 4 4
0 1 0 4 0 1 0 4 0 1 0 4 0 1 0 4
1 1 4 4 1 1 4 4 1 1 4 4 1 1 4 4
0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4

The table has a strong pattern. Notice that it is divided into several $2\times 2$ matrices, with $0$ always in the upper-left corner and the other three entries always equal. We may therefore compress the table by replacing each $2\times 2$ matrix with the common value outside its upper-left corner:

1 2 1 3 1 2 1 4 
2 2 3 3 2 2 4 4 
1 3 1 3 1 4 1 4 
3 3 3 3 4 4 4 4 
1 2 1 4 1 2 1 4 
2 2 4 4 2 2 4 4 
1 4 1 4 1 4 1 4 
4 4 4 4 4 4 4 4 

The compressed table is the value at the same position in the complete table plus one. The problem is essentially solved. With indices starting from $0$, the value at $(i,j)$ in the table, denoted by $g(i,j)$, is given by

The required SG function is $f(i,j)=g(i-1,j-1)$. Using this recurrence, the algorithm runs in $O(\log\min\{i,j\})$ time to compute $f(i,j)$.

A simple induction also shows that $g(i,j)$ is the minimum number of times one must repeatedly divide $i$ and $j$ by $2$ simultaneously to obtain two even numbers. Equivalently, form the bitwise OR of $i$ and $j$; the number of its trailing bits equal to $1$ is the same. Thus, the value can be computed directly using __builtin_ctz(~(i | j)).

In problems of this kind, once a table observation yields an SG expression, it is usually easy to prove the expression by induction. The key to solving the problem is therefore to obtain the result in some form, rather than to derive it from scratch. For example, once the result is known, the recurrence in this problem can be proved inductively as follows. Let $S_k$ be the set of SG values of the positions obtained by splitting $k$ stones into two nonempty piles. Then $f(i,j) = \operatorname{mex}(S_i \cup S_j)$, so $S_k$ satisfies the recurrence

We need to prove that $d\in S_k$ if and only if the binary representation of $(k-1)$ has bit $d$ (the lowest bit is bit $0$) equal to $1$.

Use mathematical induction. The base case $S_1=\varnothing$ is immediate. Assume the statement holds for every positive integer smaller than $k$. Then $d\in S_k$ if and only if there exist $i,j\in\mathbf N_+$ such that $i+j=k$, at least one of the bits of $(i-1)$ and $(j-1)$ at positions $d' < d$ is $1$, and both bit $d$ values are $0$. Clearly, such a split exists if and only if, considering only bits $0\sim d$, namely modulo $2^{d+1}$, the value of $(k-1)=(i-1)+(j-1)+1$ lies in the interval $[2^d,2^{d+1}-1)$. This condition is equivalent to $(k-1)$ having bit $d$ equal to $1$. The induction step follows, and the proposition is proved.

#include <iostream>
#include <vector>

int g(int i, int j) {
  return i % 2 == 0 && j % 2 == 0 ? 0 : g(i / 2, j / 2) + 1;
}

int f(int i, int j) { return g(i - 1, j - 1); }

int main() {
  int t;
  std::cin >> t;
  for (; t; --t) {
    int n;
    std::cin >> n;
    int v = 0;
    for (int i = 0; i < n / 2; ++i) {
      int x, y;
      std::cin >> x >> y;
      v ^= f(x, y);
    }
    std::cout << (v ? "YES" : "NO") << '\n';
  }
  return 0;
}

For this type of problem, one must use results about common games together with other knowledge. Suppose the first player is required to remove stones from pile $i$, and the Nim sum of all designated piles is $v$. Then the first player cannot win if and only if $a_i \le a_i\oplus v$; in other words, the number of stones in pile $i$, namely $a_i$, does not exceed the Nim sum of all piles except pile $i$, namely $a_i\oplus v$. Since the data range is small, enumerate directly the pile designated for the first-turn move. When enumerating pile $i$, each remaining pile may be selected or not selected; the numbers of ways to obtain each distinct Nim sum can be computed by DP, and it suffices to sum the counts whose final Nim sum is at least $a_i$.

#include <array>
#include <iostream>
#include <vector>

int main() {
  constexpr int M = 1e9 + 7;
  constexpr int L = 256;
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (auto& x : a) std::cin >> x;
  int res = 0;
  for (int i = 0; i < n; ++i) {
    std::array<int, L> dp = {};
    dp[0] = 1;
    for (int j = 0; j < n; ++j) {
      if (j == i) continue;
      std::array<int, L> _dp = {};
      for (int v = 0; v < L; ++v) {
        _dp[v] = (dp[v] + dp[v ^ a[j]]) % M;
      }
      dp = std::move(_dp);
    }
    for (int v = a[i]; v < L; ++v) {
      res = (res + dp[v]) % M;
    }
  }
  std::cout << res << std::endl;
  return 0;
}

Since this problem has no independent subgames, it fundamentally uses only the lemma for determining losing and winning states. Start with the simplest case. When $n\le 2$, this is Nim. When $n \ge 3$, the problem becomes more complicated. However, because only the two end piles can be operated on, let their numbers of stones be $x$ and $y$, respectively. Further, let $f(x,y)$ be the indicator of a first-player-winning state: $f(x,y)=1$ when the first player wins and $f(x,y)=0$ otherwise. It is easy to see that $f(x,y)$ satisfies the recurrence $f(x,y)=0$ if and only if, for every $s < x$ and $t < y$, we have $f(x,t)=f(s,y)=1$. When $x=0$ or $y=0$, the game has fewer than $n$ piles and the numbers of the middle piles must be considered further. Therefore, temporarily assume that $f(x,0)$ and $f(0,y)$ are known, and consider how to derive all values of $f(x,y)$ from them. This is not difficult. Consider an infinite matrix whose index set is $\mathbf N\times\mathbf N$. Computing $f(x,y)$ amounts to filling it with $0$ and $1$, under the conditions that each row and column contains at most one $0$, and that if no earlier position in the same row or column has been $0$, the position is $0$. The positions of the $0$s in each row define a function from row number $x$ to column number $y$. After trying a few examples (that is, making a table), one finds that if the unique value satisfying $f(x,0)=0$ is the $x$ value $x_0$, and the unique value satisfying $f(0,y)=0$ is the $y$ value $y_0$, then, for every $x$, the condition $f(x,y)=0$ holds when

Thus, once $x_0$ and $y_0$ are known, any position can be computed in $O(1)$ time, determining $f(x,y)$ and whether the current state is winning for the first player. The values $x_0$ and $y_0$ can be computed recursively. For example, $x_0$ is the unique solution of $f(x,0)=0$, while the value of $f(x,0)$ can be computed by removing the rightmost pile and considering only the remaining $n-1$ piles; that is, considering only the first $n-1$ piles, one can likewise compute $f_{1,n-1}(x,y)$, and evidently $f(x,0)=f_{1,n-1}(x,a_{n-1})$. Similarly, after removing the leftmost pile and computing $f_{2,n}(x,y)$, we obtain $f(0,y)=f_{2,n}(a_1,y)$. Of course, computing the inner functions $f_{1,n-1}(x,y)$ and $f_{2,n}(x,y)$ depends on functions for still smaller intervals. This is a typical interval DP. Each layer only needs to maintain the corresponding $x_0$ and $y_0$ values.

#include <array>
#include <iostream>
#include <vector>

int main() {
  // Transition helper as explained above.
  auto calc = [](int x0, int y0, int x) -> int {
    return x == x0 ? 0
                   : ((x < x0 && x < y0) || (x > x0 && x > y0)
                          ? x
                          : (x0 < y0 ? x - 1 : x + 1));
  };

  int t;
  std::cin >> t;
  for (; t; --t) {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;

    // dp[i][j][0] = the unique value x such that
    //     f_{i-1,j}(x, a_j) = 0
    // i.e. the interval game [i, j] is in a P-position
    // when a pile of size x is attached to the LEFT.
    //
    // dp[i][j][1] = the unique value y such that
    //     f_{i,j+1}(a_i, y) = 0
    // i.e. the interval game [i, j] is in a P-position
    // when a pile of size y is attached to the RIGHT.
    std::vector<std::vector<std::array<int, 2>>> dp(
        n, std::vector<std::array<int, 2>>(n));

    // Base case: single-element interval [i, i].
    // The "left" and "right" pile values both equal a[i].
    for (int i = 0; i < n; ++i) dp[i][i][0] = dp[i][i][1] = a[i];

    // Build up intervals of increasing length d.
    for (int d = 1; d < n; ++d) {
      for (int i = 0; i + d < n; ++i) {
        dp[i][i + d][0] =
            calc(dp[i][i + d - 1][1], dp[i][i + d - 1][0], a[i + d]);
        dp[i][i + d][1] = calc(dp[i + 1][i + d][0], dp[i + 1][i + d][1], a[i]);
      }
    }

    // The original game corresponds to attaching nothing on the left.
    // It is a P-position if and only if the unique value y satisfying
    //     f_{-1, n-1}(0, y) = 0
    // is y = 0.
    std::cout << (dp[0][n - 1][0] != 0) << '\n';
  }
  return 0;
}