33OJ
登录 注册

#P17527. [JAG 2026 Summer Camp #1] XOR Cycle

[JAG 2026 Summer Camp #1] XOR Cycle

题目描述

给定 2N2N 个非负整数 A1,B1,A2,B2,…,AN,BNA_1,B_1,A_2,B_2,\ldots,A_N,B_N。

判断是否存在一个非负整数序列 X=(X1,X2,…,XN)X=(X_1,X_2,\ldots,X_N),其中每个元素都小于 2302^{30},并满足以下条件。若存在,输出任意一个这样的序列。

  • 对于每个 i=1,2,…,Ni=1,2,\ldots,N,都有 $X_i\equiv (A_i\oplus X_{i-1})+(B_i\oplus X_{i-1})\pmod{2^{30}}$。

这里定义 X0=XNX_0=X_N。此外,a⊕ba\oplus b 表示 aa 与 bb 的按位异或。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤2×1051\le T\le 2\times 10^5),表示测试数据组数。接下来给出 TT 组测试数据,每组格式如下:

N
A_1 B_1
A_2 B_2
...
A_N B_N

第一行包含一个整数 NN,表示 AA 和 BB 的长度(1≤N≤2×1051\le N\le 2\times 10^5)。对于每个 i=1,2,…,Ni=1,2,\ldots,N,接下来 NN 行中的第 ii 行包含两个整数 AiA_i 和 BiB_i(0≤Ai,Bi<2300\le A_i,B_i<2^{30})。

所有测试数据的 NN 之和不超过 2×1052\times 10^5。

输出格式

对于每组测试数据,若存在这样的序列 XX,按以下格式输出 Yes,然后输出 XX:

Yes
X_1 X_2 ... X_N

否则,输出 No。

若有多个满足条件的序列 XX,可以输出其中任意一个。

3
2
4 7
1 0
1
0 1
1
536870912 536870912
Yes
3 5
Yes
1
Yes
0