← 返回题目列表

AtCoder · abc150_f

F. 异或移位

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

分数: 600 点

问题陈述

给出两个序列 a=\{a_0,\ldots,a_{N-1}\} 和 b=\{b_0,\ldots,b_{N-1}\} of N 每个非负整数。

Snuke 将选择一个整数 k 这样 0 \leq k < N 和一个整数 x 不小于 0,创建一个新的长度序列 N, a'=\{a_0',\ldots,a_{N-1}'\},如下:

  • a_i'= a_{i+k \mod N}\ XOR \ x

查找所有对 (k,x) 这样 a' 将等于 b.

什么是 \text{ XOR }?

整数的异或 A 和 B, A \text{ XOR } B,定义如下:

  • 当 A \text{ XOR } B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
例如, 3 \text{ XOR } 5 = 6。 (在基数二中: 011 \text{ XOR } 101 = 110.)

约束

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

输入

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

N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

输出

打印所有对 (k, x) 这样 a' 和 b 将相等,每对使用一行,按升序排列 k (升序 x 对于具有相同的配对 k).

如果没有这样的对,则输出应为空。


示例输入 1

3
0 2 1
1 2 3

示例输出 1

1 3

If (k,x)=(1,3),

  • a_0'=(a_1\ XOR \ 3)=1

  • a_1'=(a_2\ XOR \ 3)=2

  • a_2'=(a_0\ XOR \ 3)=3

我们有 a' = b.


示例输入 2

5
0 0 0 0 0
2 2 2 2 2

示例输出 2

0 2
1 2
2 2
3 2
4 2

示例输入 3

6
0 1 3 7 6 4
1 5 4 6 2 3

示例输出 3

2 2
5 5

示例输入 4

2
1 2
0 0

示例输出 4


没有对可以满足该条件。