Xor Shift

题目描述

给出两个长度为 $N$ 的非负整数序列 $a=\{a_0,\ldots,a_{N-1}\}$ 和 $b=\{b_0,\ldots,b_{N-1}\}$。 Snuke 会选择一个整数 $k$，使得 0 \leq k < N，以及一个不小于 $0$ 的整数 $x$，来构造一个新的长度为 $N$ 的序列 $a'=\{a_0',\ldots,a_{N-1}'\}$，定义如下：

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

找出所有使得 $a'$ 等于 $b$ 的所有对 $(k,x)$。

输入格式

标准输入的格式如下： $N$ $a_0$ $a_1$ $...$ $a_{N-1}$ $b_0$ $b_1$ $...$ $b_{N-1}$

输出格式

输出所有使得 $a'$ 与 $b$ 相等的对 $(k, x)$，每对占一行，按 $k$ 的升序输出（对于相同 $k$ 的对按 $x$ 的升序输出）。 如果不存在这样的对，则输出应为空。

3
0 2 1
1 2 3

1 3

5
0 0 0 0 0
2 2 2 2 2

0 2
1 2
2 2
3 2
4 2

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

2 2
5 5

提示

$1 \leq N \leq 2 \times 10^5$ 0 \leq a_i,b_i < 2^{30} 输入中的所有数值均为整数。如果 $(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$.
可能没有满足条件的对。

标签: AtCoder|abc150F

来源

AtCoder|abc150F