#P3491. [POI 2009] SLW-Words

[POI 2009] SLW-Words

题目描述

Let hh be a function acting on strings composed of the digits 0 and 1. The function hh transforms the string ww by replacing (independently and concurrently) every digit 0 with 1 and every digit 1 with the string "10". For example h("1001")="101110"h("1001") = "101110", h("")=""h("") = "" (i.e. hh assigns an empty string to the empty string). Note that hh is an injection, or a one - to - one function. By hkh^k we denote the function hh composed with itself kk times. In particular, h0h^0 is the identity function h0(w)=wh^0(w)=w.

We are interested in the strings of the form hk("0")h^k("0") for k=0,1,2,3,k = 0,1,2,3,\cdots. This sequence begins with the following strings:

"0", "1", "10", "101", "10110", "10110101".

We call the string xx a substring of the string yy if it occurs in yy as a contiguous (i.e. one - block) subsequence. A sequence of integers k1,k2,,knk_1,k_2,\cdots,k_n is given. Your task is to check whether a string of the form $h^{k_1}("0") \cdot h^{k_2}("0") \cdots h^{k_n}("0")$ is a substring of hm("0")h^m("0") for some mm.

输入格式

The first line of the standard input contains a single integer tt, 1t131 \leq t \leq 13, denoting the number of test units. The first line of each test unit's description contains one integer nn, 1n1000001 \leq n \leq 100000. The second line of each description holds nn non - negative integers k1,k2,,knk_1,k_2,\cdots,k_n, separated by single spaces. The sum of the numbers in the second line of any test unit description does not exceed 10000000.

输出格式

Your programme should print out tt lines to the standard output, one for each test unit. Each line corresponding to a test unit should contain one word: TAK (yes in Polish - if $h^{k_1}("0") \cdot h^{k_2}("0") \cdots h^{k_n}("0")$ is a substring of hm("0")h^m("0") for some mm in that test unit, or NIE (no in Polish) otherwise.

2
2
1 2
2
2 0

TAK
NIE