题面

链接

描述

给出两个长度为N的序列A={A0,…,AN-1}和B={B0,…,BN-1}。

zdragon将会选择一个整数k(0 <= k < N)和一个非负整数x,来生成一个新的序列C={C0,…,CN-1},满足Ci=A(i+k) mod N XOR x。

求所有满足B=C的(k,x)。

其中,XOR表示异或,参与运算的两个值,如果两个相应的二进制位相同,该位结果为0,否则为1。

例如:12 XOR 10 = 6 (1100 XOR 1010 = 0110)

输入

第一行输入包含一个正整数N(1<=N<=200000)。

第二行输入包含N个整数Ai(0<=Ai<2^30)。

第三行输入包含N个整数Bi(0<=Bi<2^30)。

输出

输出所有满足要求的(k,x),每对输出一行,按k升序输出。

若不存在,输出应该为空。

样例输入

3
0 2 1
1 2 3

样例输出

1 3

提示

当(k,x)=(1,3)时,C0=(A1 XOR 3)=1,C1=(A2 XOR 3)=2,C2=(A0 XOR 3)=3。

满足B=C。

思路

k 的作用就是把 A 数组平移

根据异或的性质 Bi = Aj ^ x

即 Bi ^ Aj = x

对于位移后每一对匹配的 A, B 都要满足异或相等

这种位运算的题目一般技巧就是把每一位拆开单独看

这样就只有 0, 1

不妨固定 B 数组, 那么 A 数组只有两种情况

要么对应位全相等,要么全相反,分类讨论满足一种即可

再加上 A 可以平移,把 A 看着一个环在旋转,一般情况就是倍长

此时就可以想到用 KMP 匹配, 在倍长的 A 中寻找 B 完全匹配的起点

然后就可以意会了吧,懒得敲了

复杂度 O(n log(maxA))

代码