← 返回题目列表

AtCoder · arc124_b

B. 异或匹配2

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给出的是序列 a 和 b,每个长度 N,由非负整数组成。的 i第一个元素 a 和 b 是 a_i 和 b_i。

非负整数 x 据说是 好 当满足以下条件时:

  • 条件:可以排列 b 这样 a_i \text{ XOR } b_i = x 对于每个整数都成立 i 这样 1 \leq i \leq N,其中 \text{XOR } 是按位异或。

按升序列出所有好的整数。

什么是 \mathrm{XOR}?

按位 \mathrm{XOR} 整数 x 和 y, x\ \mathrm{XOR}\ y,定义如下:

  • 当 x\ \mathrm{XOR}\ y 以二为基数写入,即 2^k的地点 (k \geq 0) 是 1 如果恰好是其中之一 x 和 y is 1,和 0 否则。
例如,我们有 3\ \mathrm{XOR}\ 5 = 6 (以二为基数: 011\ \mathrm{XOR}\ 101 = 110).

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 2000
  • 0 \leq a_i, b_i < 2^{30}

输入

输入由标准输入按以下格式给出:

N
a_1 \cdots a_N
b_1 \cdots b_N

输出

在第一行中,打印 K,好整数的数量。 然后,打印 K 更多行。在 i- 其中第一个 K 行,打印 i- 第一个最小的好整数。


示例输入 1

3
1 2 3
6 4 7

示例输出 1

1
5
  • 如果我们排列 b 进入 (4, 7, 6),我们有 a_1 \text{ XOR } b_1 = a_2 \text{ XOR } b_2 = a_3 \text{ XOR } b_3 = 5,所以 5 是一个很好的整数。没有其他好的整数。

示例输入 2

2
0 1
0 2

示例输出 2

0

示例输入 3

24
14911005 70152939 282809711 965900047 168465665 337027481 520073861 20800623 934711525 944543101 522277111 580736275 468493313 912814743 99651737 439502451 365446123 198473587 285587229 253330309 591640417 761745547 247947767 750367481
805343020 412569406 424258892 329301584 123050452 1042573510 1073384116 495212986 158432830 145726540 623594202 836660574 380872916 722447664 230460104 718360386 620079272 109804454 60321058 38178640 475708360 207775930 393038502 310271010

示例输出 3

8
107543995
129376201
139205201
160626723
312334911
323172429
481902037
493346727