这题转换有点神仙的。
Link。
首先，\(x\)
可以直接根据序列中两个对应的数直接算出来。
然后发现这个 \(k\) 实际上相当于把
\(a\) 循环位移了。假设循环位移之后的
\(a\) 序列变为 \(a'\)，那么实际上有：
\[
a'_0\otimes x=b_0
\]
即：
\[
x=a'_0\otimes b_0
\]
我们把它代入 \(i=1\) 中：
\[
a'_1\otimes a'_0\otimes b_0=b_1
\]
即：
\[
a'_1\otimes a'_0=b_1\otimes b_0
\]
我们发现这已经变成了一个和 \(x\)
无关的式子了。也就是说，我们只关心 \(a,b\)
相邻两数的异或值。那么我们不妨把这个预处理出来，得到序列 \(p,q\)。现在我们就将异或相等问题转化为相等问题了。因此现在直接跑一遍
KMP 即可。
最后 \(x\)
就用刚才的方式倒推回去即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| int n;
int a[MAXN], b[MAXN];
int d[MAXN], p[MAXN * 3];
int pi[MAXN * 3];
void get_nxt()
{
pi[0] = 0;
for(int i = 1; i <= 3 * n + 1; i++)
{
int j = pi[i - 1];
while(j > 0 && p[i] != p[j + 1]) j = pi[j];
if(p[i] == p[j + 1] && j + 1 < i) pi[i] = j + 1;
}
}
signed main()
{
read(n);
for(int i = 0; i < n; i++) read(a[i]);
for(int i = 0; i < n; i++) read(b[i]);
for(int i = 0; i < n; i++) d[i] = a[i] ^ a[(i + 1) % n];
for(int i = 0; i < n; i++) p[i] = b[i] ^ b[(i + 1) % n];
for(int i = n; i >= 1; i--) p[i] = p[i - 1];
p[n + 1] = -1;
for(int i = 1; i <= n; i++) p[i + n + 1] = d[i - 1];
for(int i = 1; i <= n; i++) p[i + n * 2 + 1] = d[i - 1];
get_nxt();
for(int i = 2 * n + 1; i <= 3 * n; i++)
if(pi[i] == n)
printf("%d %d\n", i - 2 * n - 1, a[i - 2 * n - 1] ^ b[0]);
return 0;
}
|
