分数: 1000 点
问题陈述
给你一个正整数 N,一个正整数 X,以及排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N)。仅 X 以二进制给出,而 N 和元素 P 以十进制给出。
判断是否存在非负整数序列 A=(A_1,A_2,\ldots,A_N) 和 B=(B_1,B_2,\ldots,B_N) 满足以下所有条件。
- 两者 A 和 B 是严格递增序列。
- A_{P_i}=B_i \oplus X 成立 i=1,2,\ldots,N.
这里,二元运算符 \oplus 表示非负整数的按位异或。
你被给予 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 以二进制形式给出,不带前导零。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N X P_1 P_2 \ldots P_N
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,输出 Yes 如果存在 A 和 B 满足所有条件,并且 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
对于第一个测试用例,例如, A=(2,3,5,7) 和 B=(0,2,6,7) 满足条件。