C - Mixture Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 種類の薬品 1,2,\dots,N があります。あなたの目標はこれらが全て混ざった状態にすることです。
0, 1 からなる長さ 2^N-1 の文字列 S が与えられます。この文字列は次の情報を表します。

  • まず、 1 種類以上の薬品が混ざった状態 i ( 1 \le i \le 2^N-1 ) を次のように定義する。
    • i を 2 進法で表記した際に下から k ( 1 \le k \le N ) 桁目が 1 である、またその時に限り、薬品 k が含まれている。
    • 例えば、 13 を 2 進法で表記すると 1101_{(2)} となるため、状態 13 は薬品 1,3,4 が混ざった状態を表現します。
  • S の i 文字目が 0 であるとき、状態 i は 安全 である。
  • S の i 文字目が 1 であるとき、状態 i は 危険 である。

あなたは次の操作を使って薬品を混ぜ合わせます。

  • まず、空の瓶を用意する。
  • 次に、以下を繰り返す。
    • まだ瓶に注いでいない薬品を 1 種類選択し、瓶に注ぐ。
    • この時、瓶の中で混ざった薬品が危険な状態であってはならない。

この操作によって全ての薬品が混ざった状態を作れるか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • T は 1 以上 40000 以下の整数
  • N は 1 以上 18 以下の整数
  • S は 0, 1 からなる長さ 2^N-1 の文字列
  • ひとつの入力に含まれる |S| = 2^N-1 の総和は 5 \times 10^5 を超えない

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i は i 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。

N
S

出力

T 行出力せよ。i 行目 には i 番目のテストケースに対する答えを出力せよ。
各テストケースについて、全ての薬品が混ざった状態を作れるなら Yes 、作れないなら No と出力せよ。

入力例 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

出力例 1

Yes
No
No
Yes
Yes

この入力には 5 個のテストケースが含まれます。

1 番目のケースは次の通りです。

  • 3 種類の薬品が存在する。
  • 薬品 1,2 が混ざった状態 3 のみが危険で、他の状態は安全である。
  • 例えば、以下の手順で全ての薬品が混ざった状態を作ることができます。
    • はじめに、瓶に薬品 2 を注ぐ。瓶の中で薬品 2 のみが混ざっており、これは状態 2 なので安全である。
    • 次に、瓶に薬品 3 を注ぐ。瓶の中で薬品 2,3 が混ざっており、これは状態 6 なので安全である。
    • 最後に、瓶に薬品 1 を注ぐ。瓶の中で薬品 1,2,3 が混ざっており、これは状態 7 なので安全である。

2 番目のケースは次の通りです。

  • 3 種類の薬品が存在する。
  • 薬品 1,2 が混ざった状態 3 、薬品 1,3 が混ざった状態 5 、薬品 2,3 が混ざった状態 6 が危険で、他の状態は安全である。
  • このケースについて、全ての薬品が混ざった状態を作ることはできません。

3 番目のケースは次の通りです。

  • 1 種類の薬品が存在する。
  • 薬品 1 のみが混ざった状態 1 が危険であるため、全ての薬品が混ざった状態を作ることはできません。

Score : 350 points

Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

  • First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
    • When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
    • For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
  • When the i-th character of S is 0, state i is safe.
  • When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

  • First, prepare an empty bottle.
  • Next, repeat the following:
    • Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
    • At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

You are given T test cases; solve each of them.

Constraints

  • T is an integer between 1 and 40000, inclusive.
  • N is an integer between 1 and 18, inclusive.
  • S is a string of length 2^N-1 consisting of 0 and 1.
  • The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

\mathrm{case}_i represents the i-th test case. Each test case is given in the following format:

N
S

Output

Output T lines. The i-th line should contain the answer for the i-th test case.
For each test case, if it is possible to create a state where all chemicals are mixed, print Yes; otherwise, print No.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

  • There are three types of chemicals.
  • Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
  • For example, you can create a state where all chemicals are mixed with the following procedure:
    • First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
    • Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
    • Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

  • There are three types of chemicals.
  • State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
  • For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

  • There is one type of chemical.
  • Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.