/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
正整数 N と正整数 X，(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) が与えられます．X のみ二進法で与えられ，N と P の要素は十進法で与えられます．
以下の条件を全て満たすような非負整数列 A=(A_1,A_2,\ldots,A_N) と B=(B_1,B_2,\ldots,B_N) が存在するか判定してください．
- A,B は共に狭義単調増加列である．
- i=1,2,\ldots,N に対し A_{P_i}=B_i \oplus X が成り立つ．
ただし，二項演算子 \oplus は非負整数同士の bit 毎の排他的論理和を表します．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1\le T\le 10^5
- 2\le N\le 2\times 10^5
- 1\le X < 2^{10^6}
- P は (1,2,\ldots,N) の順列
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 全てのテストケースにおける X の二進法における桁数の総和は 10^6 以下
- T,N,P_i は十進法で与えられる
- X は leading zero がない二進法で与えられる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる．
N X P_1 P_2 \ldots P_N
出力
各テストケースに対する答えを順に改行区切りで出力せよ．
各テストケースについて，条件を全て満たす A と B が存在する場合は Yes を，存在しない場合は No を出力せよ．
入力例 1
3 4 101 3 4 2 1 4 100 4 3 2 1 8 1101011 3 5 4 1 2 6 8 7
出力例 1
Yes No Yes
1 番目のテストケースについて，例えば A=(2,3,5,7) と B=(0,2,6,7) が条件を満たします．
Score : 1000 points
Problem Statement
You are given a positive integer N, a positive integer X, and a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N). Only X is given in binary, while N and the elements of P are given in decimal.
Determine whether there exist sequences of non-negative integers A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N) satisfying all of the following conditions.
- Both A and B are strictly increasing sequences.
- A_{P_i}=B_i \oplus X holds for i=1,2,\ldots,N.
Here, the binary operator \oplus denotes the bitwise XOR of non-negative integers.
You are given T test cases; solve each of them.
Constraints
- 1\le T\le 10^5
- 2\le N\le 2\times 10^5
- 1\le X < 2^{10^6}
- P is a permutation of (1,2,\ldots,N).
- The sum of N over all test cases is at most 2\times 10^5.
- The sum of the number of digits of X in binary over all test cases is at most 10^6.
- T,N,P_i are given in decimal.
- X is given in binary without leading zeros.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N X P_1 P_2 \ldots P_N
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, output Yes if there exist A and B satisfying all the conditions, and No otherwise.
Sample Input 1
3 4 101 3 4 2 1 4 100 4 3 2 1 8 1101011 3 5 4 1 2 6 8 7
Sample Output 1
Yes No Yes
For the first test case, for example, A=(2,3,5,7) and B=(0,2,6,7) satisfy the conditions.