#P17527. [JAG 2026 Summer Camp #1] XOR Cycle
[JAG 2026 Summer Camp #1] XOR Cycle
题目描述
给定 个非负整数 。
判断是否存在一个非负整数序列 ,其中每个元素都小于 ,并满足以下条件。若存在,输出任意一个这样的序列。
- 对于每个 ,都有 $X_i\equiv (A_i\oplus X_{i-1})+(B_i\oplus X_{i-1})\pmod{2^{30}}$。
这里定义 。此外, 表示 与 的按位异或。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 (),表示测试数据组数。接下来给出 组测试数据,每组格式如下:
N
A_1 B_1
A_2 B_2
...
A_N B_N
第一行包含一个整数 ,表示 和 的长度()。对于每个 ,接下来 行中的第 行包含两个整数 和 ()。
所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,若存在这样的序列 ,按以下格式输出 Yes,然后输出 :
Yes
X_1 X_2 ... X_N
否则,输出 No。
若有多个满足条件的序列 ,可以输出其中任意一个。
3
2
4 7
1 0
1
0 1
1
536870912 536870912
Yes
3 5
Yes
1
Yes
0