#P5653. [ABC150F] Xor Shift

    ID: 4654 传统题 1000ms 256MiB 尝试: 6 已通过: 3 难度: 6 上传者: 标签>CF1900普及+/提高-差分转化异或抵消复制数组处理环KMP600

[ABC150F] Xor Shift

题面翻译

题目描述

给定两个长度为 nn 的序列 a={a0,a1,⋯ ,an−1}a=\{a_0,a_1,\cdots,a_{n-1}\} 和 b={b0,b1,⋯ ,bn−1}b=\{b_0,b_1,\cdots,b_{n-1}\},输出所有有序数对 (k,x)(k,x) ,满足:

  1. 0≤k<n0\leq k<n 且 x≥0x\geq 0。
  2. 序列 a′=ba'=b,其中 $a'_i = a_{i+k\bmod n}\operatorname{xor} x\ (0\leq i<n)$,“xor⁡\operatorname{xor}”表示按位异或。

输入格式

第一行一个整数 nn。 第二行 nn 个整数,依次是 a0,a1,⋯ ,an−1a_0,a_1,\cdots,a_{n-1}。 第三行 nn 个整数,依次是 b0,b1,⋯ ,bn−1b_0,b_1,\cdots,b_{n-1}。

输出格式

输出所有满足条件有序对 (k,x)(k,x),每对占一行。如果没有满足条件的有序对,输出为空。

数据范围

1≤n≤2×1051\leq n\leq 2\times 10^5,0≤ai,bi<2300\leq a_i,b_i<2^{30}。

样例 #1

样例输入 #1

3
0 2 1
1 2 3

样例输出 #1

1 3

样例 #2

样例输入 #2

5
0 0 0 0 0
2 2 2 2 2

样例输出 #2

0 2
1 2
2 2
3 2
4 2

样例 #3

样例输入 #3

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

样例输出 #3

2 2
5 5

样例 #4

样例输入 #4

2
1 2
0 0

样例输出 #4