原題來自:ZJOI 2009
在研究過 Nim 游戲及各種變種之后,Orez 又發(fā)現(xiàn)了一種全新的取石子游戲,這個游戲是這樣的:
有 $n$ 堆石子,將這 $n$ 堆石子擺成一排。游戲由兩個人進行,兩人輪流操作,每次操作者都可以從最左或最右的一堆中取出若干顆石子,可以將那一堆全部取掉,但不能不取,不能操作的人就輸了。
Orez 問:對于任意給出一個初始一個局面,是否存在先手必勝策略。
第一行為一個整數(shù) $T$,表示有 $T$ 組測試數(shù)據(jù)。\n對于每組測試數(shù)據(jù),第一行為一個整數(shù) $n$,表示有 $n$ 堆石子,第二行為 $n$ 個整數(shù) $a_i$ ,依次表示每堆石子的數(shù)目。
對于每組測試數(shù)據(jù)僅輸出一個整數(shù) $0$ 或 $1$。其中 $1$ 表示有先手必勝策略,$0$ 表示沒有。
1 4 3 1 9 4
0
數(shù)據(jù)范圍與提示:
對于 30% 的數(shù)據(jù),$n\le 5,a_i\le 10^5$ ;
對于全部數(shù)據(jù),$1≤T≤10,1≤n≤1000$,每堆石子的個數(shù)小于等于 $10^9$ 。