P2599 [ZJOI2009] Stone-Taking Game

After studying the Nim game and its variants, Orez discovered a brand-new stone-taking game, defined as follows: There are $n$ piles of stones arranged in a row. Two players take turns. On each turn, a player may take any positive number of stones from either the leftmost pile or the rightmost pile; the entire pile may be taken, but taking zero stones is not allowed. The player who cannot move loses. Orez asks: given any initial position, does there exist a winning strategy for the first player?

The first line contains an integer $T$, the number of test cases. For each test case: - The first line contains an integer $n$, the number of piles. - The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, where $a_i$ is the number of stones in the $i$-th pile.

For each test case, output a single integer $0$ or $1$. Here, $1$ means there exists a winning strategy for the first player, and $0$ means there is not.

- For $30\%$ of the testdata, $n \le 5$, $a_i \le 10^5$. - For $100\%$ of the testdata, $1 \le T \le 10$, $1 \le n \le 1000$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5