Problem:


Score : 600 points

Problem Statement

Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.

Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:

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

Find all pairs (k,x) such that a' will be equal to b.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq a_i,b_i < 2^{30}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).

If there are no such pairs, the output should be empty.

Sample Input 1

3
0 2 1
1 2 3

Sample Output 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

and we have a' = b.

Sample Input 2

5
0 0 0 0 0
2 2 2 2 2

Sample Output 2

0 2
1 2
2 2
3 2
4 2

Sample Input 3

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

Sample Output 3

2 2
5 5

Sample Input 4

2
1 2
0 0

Sample Output 4

No pairs may satisfy the condition.



Sample input:
3
0 2 1
1 2 3


Sample output:
1 3

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

L = 30
for l in range(L):
    HashA = 0
    for i, a in enumerate(A):
        if (1<<l)&a:
            HashA = (HashA + H[i]) % h

    HashB = 0
    for i, a in enumerate(B):
        if (1<<l)&a:
            HashB = (HashB + H[i]) % h
    
    for k in range(N):
        if (HashA+HashB)%h == allSum:
            ans[k] += (1<<l)
        elif HashA != HashB:
            ok[k] = False
        HashB = (HashB * b) % h
        if (1<<l)&B[-k-1]:
            HashB = (HashB + h - H[N] + 1) % h

for k in range(N):
    if ok[k]:
        print(k, ans[k])

Submission status: Accepted

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + s[i]) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[a[i%N]^a[(i+1)%N] for i in range(2*N)]
d=[b[i]^b[(i+1)%N] for i in range(N)]
P=RollingHash(c,97,10**9+7)
Q=RollingHash(d,97,10**9+7)

for k in range(N):
    if P.get(k,k+N)==Q.get(0,N):
        x=b[0]^a[k]
        print(k,x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

for k in ans:
    print(k, A[k]^B[0])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

h = 10**11+7
b = 10**7+7

H = [1]
for _ in range(N):
    H.append((H[-1]*b)%h)

allSum = 0
for i in range(N):
    allSum = (allSum + H[i]) % h

ok = [True]*N
ans = [0]*N

C = []
D = []
for i in range(N):
    C.append(A[i-1]^A[i])
    D.append(B[i-1]^B[i])


HashA = 0
for i, a in enumerate(C):
    HashA = (HashA + a*H[i]%h) % h

HashB = 0
for i, a in enumerate(D):
    HashB = (HashB + a*H[i]%h) % h

ans = []
for k in range(N):
    if HashA == HashB:
        ans.append(k)
    HashB = (HashB * b) % h
    HashB = (HashB + (1-H[N])*D[-k-1] % h) % h

for k in ans:
    print(k, A[k]^B[0])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


a = convert(al)
b = convert(bl)


def Z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = z[i - l] if z[i - l] < r - i else r - i - 1
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


Z = Z_algorithm(b + [-1] + a + a)[n + 1:n + n + 1]

K = [i for i, x in enumerate(Z) if x == n]
X = [al[k] ^ bl[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


a = convert(al)
b = convert(bl)


def Z_algorithm(s):
    n = len(s)
    z = [0] * n
    l, r = 0, 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r - i - 1, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
    return z


Z = Z_algorithm(b + [-1] + a + a)[n + 1:n + n + 1]

K = [i for i, x in enumerate(Z) if x == n]
X = [al[k] ^ bl[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

Submission status: Accepted

Solution code:
def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1
    while j < len(word):
        matched = word[i] == word[j]
        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i
    return table

def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0
    results = []
    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
            if p == len(word):
                p = table[p]
                results.append((i-len(word), i))
        elif p == 0:
            i += 1
        else:
            p = table[p]
    return results

N, = map(int, input().split())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))
A = []
B = []
for i in range(2*N-1):
    A.append(As[i%N] ^ As[(i+1)%N])
    if i < N:
        B.append(Bs[i%N] ^ Bs[(i+1)%N])
for k, l in kmp_search(A, B):
    print(k, As[k] ^ Bs[0])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

# 左の箱（パターンにあたる）と右の箱（対象）が連動して動く
# 文字が同じ限り右に広げて、lcpを記録しながら左に縮めていく感じ
# 縮められなくなったら、topを右の箱の左端にして、左の箱を0までずらす
# 箱ができていない（幅が0）のときは、右の箱を1つ右に

def ZAlgorithm(aa):
    target = aa
    # s = input()
    len_t = len(target)
    lcp = [-1] * len_t
    top = 1  # 右の箱において、左の箱の0に対応する点
    left = 0  # 左の箱の左端(本当はここでので宣言は不要だけど理解の為)
    right = 0  # 左の箱の右端
    lcp[0] = 0
    while top < len_t:
        # 箱を右に広げていく
        while top + right < len_t and target[right] == target[top + right]:
            right += 1
        # 右の箱左端のlcpを記録
        lcp[top] = right
        left = 1
        # 箱の幅が0だったらtopを動かして、このターン終了
        if right == 0:
            top += 1
            continue
        # lcpを記録しながら箱を左に縮めていく（最初の条件重要）
        while left + lcp[left] < right and left < right:
            lcp[top + left] = lcp[left]
            left += 1
        # topを右の箱の左端にして、左の箱を0まで戻す
        top += left
        right -= left
        left = 0  # これも本当は不要
    return lcp

def main():
    # 「aを左にシフト」＝「bを右にシフト」
    # 左にシフトは面倒なのでbを右に動かす
    # 動かした(下記は2つシフトしたとき)結果
    #  a0  a1  a2  a3  a4
    # xor xor xor xor xor
    #  x   x   x   x   x
    #  =   =   =   =   =
    #  b3  b4  b0  b1  b2
    # と、なっていればよい。ここで、xorをただの足し算に置き換えて考える
    #  a0  a1  a2  a3  a4
    #  +   +   +   +   +
    #  x   x   x   x   x
    #  =   =   =   =   =
    #  b3  b4  b0  b1  b2
    # 具体例で
    #  4   6   3   7   2
    #  +   +   +   +   +
    #  1   1   1   1   1
    #  =   =   =   =   =
    #  5   7   4   8   3
    # このとき、aの増減とbの増減は一致する
    # aの増減・・・末尾から(+2) 4 (+2) 6 (-3) 3 (+4) 7 (-5) 2
    # bの増減・・・末尾から(+2) 5 (+2) 7 (-3) 4 (+4) 8 (-5) 3
    # これはxorでも同様のことがいえる
    # よって、a,bそれぞれの隣接xorのリストを作る
    # aを2つ並べて(ループするから)、bを右にシフトしながら一致する位置を探す
    # 一致する位置を探すのはZ-Algorithmを使った
    # シフト量が分かれば、対応する1組のa,bからxも分かる
    # らしいが、こんなの思いつかんわ!!

    inf = pow(2, 31)
    n = II()
    aa = LI()
    bb = LI()
    ax = [aa[i - 1] ^ aa[i] for i in range(n)]
    bx = [bb[i - 1] ^ bb[i] for i in range(n)]
    # print(ax)
    # print(bx)
    ll = ZAlgorithm(bx + [inf] + ax + ax[:-1])
    # lcp・・・length common prefixみたいな?
    for shift, lcp in enumerate(ll[n + 1:]):
        if lcp == n: print(shift, aa[shift] ^ bb[0])

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
条件を満たすとき
a_{(i+k) mod N} xor X = b_i
a_{(i+k+1) mod N} xor X = b_{i+1}が成り立つ
よって,a_{(i+k) mod N} xor a_{(i+k+1) mod N} = b_i xor b_{i+1}
各iについてb_i xor b_{i+1}を求めたリストをB,
数列aを2つ繋げて,a_i xor a_{i+1}を求めたリストをA,
BとAを繋げたリストをCとする.
Z_algorithmを用いるとSとS[i:|S|-1]の最長共通接頭辞の長さがO(N)で出せるので,
CにZ_algorithmを用いると,最初のBとAの共通部分列の長さが出せる.
共通部分列の長さがN以上のとき,条件を満たす.
"""

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
 
        #再利用部分
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

n = I()
a = LI()
b = LI()

x = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
y = [b[i%n]^b[(i+1)%n] for i in range(n)]
z = Z_algorithm(y+x)
for i in range(n,2*n):
    if z[i] >= n:
        k = i-n
        x = a[k] ^ b[0]
        print(k,x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def Z_algorithm(s):
    n = len(s)
    Z = [0]*n
    Z[0] = n
    i,j = 1,0
    while i < n:
        while i+j < n and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
 
        #再利用部分
        while i+k < n and k+Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

n = I()
a = LI()
b = LI()

x = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
y = [b[i%n]^b[(i+1)%n] for i in range(n)]
z = Z_algorithm(y+x)
for i in range(n,2*n):
    if z[i] >= n:
        k = i-n
        x = a[k] ^ b[0]
        print(k,x)

Submission status: Accepted

Solution code:
import sys
from operator import xor
from functools import reduce
readline = sys.stdin.readline

mod = 10**18+3
base = 10**9+9
def rollinghash(S):
    N = len(S)
    has = [0]*(N+1)
    power = [1]*(N+1)
    for i in range(N):
        s = S[i]
        has[i+1] = (has[i]*base + s)%mod
        power[i+1] = power[i]*base%mod
    return has, power
 
def rh(i, j):
    return (has[j] - has[i]*power[j-i])%mod

def rotate(k):
    pass

N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
CA = [a1^a2 for a1, a2 in zip(A, A[1:])]
CA.append(A[0]^A[-1])
CB = [a1^a2 for a1, a2 in zip(B, B[1:])]
CB.append(B[0]^B[-1])

rA = [1+ca for ca in CA]
has, power = rollinghash(rA)
R = rh(0, N)
    
HA = [None]*N
suf = pow(base, N-1, mod)
for i in range(N):
    HA[i] = R
    R = ((R-suf*rA[i])*base + rA[i])%mod

rB = [1+cb for cb in CB]
has, power = rollinghash(rB)
R = rh(0, N)

Ans = []
for i in range(N):
    if HA[i] == R:
        Ans.append((i, A[i]^B[0]))

if Ans:
    print('\n'.join(' '.join(map(str, a)) for a in Ans))

Submission status: Accepted

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + s[i]) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[a[i%N]^a[(i+1)%N] for i in range(2*N)]
d=[b[i]^b[(i+1)%N] for i in range(N)]
P=RollingHash(c,96,10**9+7)
Q=RollingHash(d,96,10**9+7)

for k in range(N):
    if P.get(k,k+N)==Q.get(0,N):
        x=b[0]^a[k]
        print(k,x)

Submission status: Accepted

Solution code:
def check(ccc, ddd, e, ans):
    m = 2147483647
    g = 1000000007
    for l in range(e):
        cl = ccc[l]
        if any(c != cl for c in ccc[l::e]):
            return
        dl = ddd[l]
        if any(d != dl for d in ddd[l::e]):
            return
    s = 0
    for c in ccc[:e]:
        s = (s * g + c) % m
    t = 0
    for d in ddd[:e]:
        t = (t * g + d) % m
    u = pow(g, e, m)
    for h in range(e):
        if s == t:
            bh = bbb[h]
            ans.update(((i - h) % n, aaa[i] ^ bh) for i in range(0, n, e))
            return
        t = (t * g + ddd[(e + h) % n] - ddd[h] * u) % m


def solve(n, aaa, bbb):
    ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
    ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]

    ans = set()

    e = 1
    while e * e <= n:
        if n % e != 0:
            e += 1
            continue
        check(ccc, ddd, e, ans)
        check(ccc, ddd, n // e, ans)
        e += 1

    return ans


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in sorted(ans)))

Submission status: Accepted

Solution code:
import sys
BASE, MOD = 80408696819889532, (1<<61)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			h[i+1] = v = (v * base + s[i]) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if n == 1:
	print(0, a[0]^b[0])
	sys.exit()
x = [a[n-1]^a[0]]
y = [b[n-1]^b[0]]
for i in range(n-1):
	x.append(a[i]^a[i+1])
	y.append(b[i]^b[i+1])

rh_x, rh_y = RollingHash(x, BASE, MOD), RollingHash(y, BASE, MOD)
for k in range(n):
	if rh_y.concatenate(n-k, n, 0, n-k) == rh_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

C = [a1^a2 for a1, a2 in zip(A, A[1:])] + [A[0]^A[-1]]
C = C + C
D = [b1^b2 for b1, b2 in zip(B, B[1:])] + [B[0]^B[-1]]

K = []
k = 0
while k < N:
  next_k = k
  is_first = True
  for i in range(N):
    if is_first and i>0 and C[k+i]==D[0]:
      next_k = k + i
      is_first = False
    if C[k+i] != D[i]:
      if next_k == k:
        k = k + i + 1
      else:
        if D[k+i-next_k] == C[k+i]:
          k = next_k
        else:
          k = k + i + 1
      break
  
  if i == N-1:
    K.append(k)
    if next_k == k:
      break
    else:
      k = next_k
      if len(K) == 2:
        diff = K[1] - K[0]
        while K[-1] < N:
          K.append(K[-1]+diff)
      
        _ = K.pop()
        break

for k in K:
  print(k, A[k]^B[0])

Submission status: Accepted

Solution code:
def Z(S):
    res = [0]*len(S)
    res[0] = len(S)
    i = 1
    j = 0
    while i < len(S):
        while i+j < len(S) and S[j] == S[i+j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < len(S) and k+res[k] < j:
            res[i+k] = res[k]
            k += 1
        i += k
        j -= k
    return res

N = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
S = [0]*N
T = [0]*N
for i in range(N):
    S[i] = a[i]^a[(i+1)%N]
    T[i] = b[i]^b[(i+1)%N]
s = 0
t = 0
for i in range(N):
    s += S[i]
    t += T[-i-1]
    if s==t:
        break

ans = []
z = Z(S)
for j in range(N):
    if z[j]==N-j:
        ans.append([(j+i+1)%N,a[0]^b[(-j-i-1)%N]])
ans.sort()
if s!=t:
    ans = []
for s in ans:
    print(*s)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            if i+z[i-c] < c+z[c]:
                z[i] = z[i-c]
            else:
                j = max(0,c+z[c]-i)
                while i+j < n and s[j] == s[i+j]:
                    j += 1
                z[i] = j
                c = i
        return z
    n = I()
    a = LI()
    b = LI()
    a_xor = [a[i%n]^a[(i+1)%n] for i in range(2*n)]
    b_xor = [b[i%n]^b[(i+1)%n] for i in range(n)]
    b_xor += a_xor
    z = Z_algorithm(b_xor)
    for k in range(n):
        i = n+k
        x = b[0]^a[k]
        if z[i] >= n:
            print(k,x)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
BASE, MOD1, MOD2 = (1<<30), (1<<61)-1, (1<<31)-1

class RollingHash():
	def __init__(self, s, base, mod):
		self.mod = mod
		self.pw = pw = [1]*(len(s)+1)

		l = len(s)
		self.h = h = [0]*(l+1)

		v = 0
		for i in range(l):
			h[i+1] = v = (v * base + s[i]) % mod
		v = 1
		for i in range(l):
			pw[i+1] = v = v * base % mod

	# [l. r)
	def get(self, l, r):
		return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod

	def concatenate(self, l1, r1, l2, r2):
		return (self.get(l1, r1) * self.pw[r2-l2] + self.get(l2, r2)) % self.mod


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
if n == 1:
	print(0, a[0]^b[0])
	sys.exit()
x = [a[n-1]^a[0]]
y = [b[n-1]^b[0]]
for i in range(n-1):
	x.append(a[i]^a[i+1])
	y.append(b[i]^b[i+1])

rh1_x, rh1_y = RollingHash(x, BASE, MOD1), RollingHash(y, BASE, MOD1)
rh2_x, rh2_y = RollingHash(x, BASE, MOD2), RollingHash(y, BASE, MOD2)
for k in range(n):
	if rh1_y.concatenate(n-k, n, 0, n-k) == rh1_x.get(0, n) and rh2_y.concatenate(n-k, n, 0, n-k) == rh2_x.get(0, n):
		print(k, a[0]^b[(n-k)%n])

Submission status: Accepted

Solution code:
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)

        l = len(s)
        self.h = h = [0]*(l+1)

        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + s[i]) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
c=[a[i%N]^a[(i+1)%N] for i in range(2*N)]
d=[b[i]^b[(i+1)%N] for i in range(N)]
P=RollingHash(c,97,10**9+7)
Q=RollingHash(d,97,10**9+7)

for k in range(N):
    if P.get(k,k+N)==Q.get(0,N):
        x=b[0]^a[k]
        print(k,x)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# (a,b,c,d) -> (ab,bc,cd,da) と変換
# xor x で不変量になる

N = int(readline())

A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

def convert(A):
    return [x ^ y for x,y in zip(A,A[1:])] + [A[-1] ^ A[0]]

C = convert(A); D = convert(B)

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    A.extend(A)
    mod1 = 10**9+7
    mod2 = 10**9+9
    b1 = 1007
    b2 = 2009
    H1 = H2 = 0
    for i in range(N-1):
        tmp = B[i] ^ B[i+1]
        #print(tmp)
        H1 = (H1 + pow(b1, N-i-2, mod1) * tmp)%mod1
        H2 = (H2 + pow(b2, N-i-2, mod2) * tmp) % mod2

    h1 = h2 = 0
    for i in range(N-1):
        tmp = A[i] ^ A[i+1]
        #print(tmp)
        h1 = (h1 + pow(b1, N-i-2, mod1) * tmp)%mod1
        h2 = (h2 + pow(b2, N-i-2, mod2) * tmp) % mod2
    #print(H1, h1, H2, h2)
    if h1 == H1 and h2 == H2:
        print(0, A[0]^B[0])
    for k in range(1, N):
        tmp_plus = A[N+k-2] ^ A[N+k-1]
        tmp_minus = A[k-1] ^ A[k]
        #print(k, tmp_plus, tmp_minus)
        h1 = ((h1 * b1)%mod1 + tmp_plus - (tmp_minus * pow(b1, N-1, mod1))%mod1) % mod1
        h2 = ((h2 * b2) % mod2 + tmp_plus - (tmp_minus * pow(b2, N-1, mod2)) % mod2) % mod2
        #print(H1, h1, H2, h2)
        if h1 == H1 and h2 == H2:
            print(k, A[k] ^ B[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

base = 123
mod = 10**9+7
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
base_m = pow(base, N-1, mod)
ans = [True]*N
for k in range(30):
    tmp = []
    mask = 1<<k
    a_k = []
    a_k_r = []
    b_k = []
    for i in range(N):
        if a[i]&mask:
            a_k.append(1)
            a_k_r.append(0)
        else:
            a_k.append(0)
            a_k_r.append(1)
        if b[i]&mask:
            b_k.append(1)
        else:
            b_k.append(0)
    b_hash = b_k[0]
    a_hash = a_k[0]
    a_hash_r = a_k_r[0]
    for i in range(1, N):
        b_hash = (b_hash*base+b_k[i])%mod
        a_hash = (a_hash*base+a_k[i])%mod
        a_hash_r = (a_hash_r*base+a_k_r[i])%mod
    for i in range(N):
        if a_hash == b_hash or a_hash_r == b_hash:
            pass
        else:
            ans[i] = False
        a_hash = ((a_hash-a_k[i]*base_m)*base+a_k[i])%mod
        a_hash_r = ((a_hash_r-a_k_r[i]*base_m)*base+a_k_r[i])%mod
for i in range(N):
    if ans[i]:
        x = a[i]^b[0]
        print(i, x)

Submission status: Accepted

Solution code:
N = int(input())
AS = list(map(int, input().split()))
BS = list(map(int, input().split()))

AXOR = [AS[i] ^ AS[(i+1) % N] for i in range(N)]
BXOR = [BS[i] ^ BS[(i+1) % N] for i in range(N)]

def getZarr(string, z): 
    n = len(string) 
  
    # [L,R] make a window which matches 
    # with prefix of s 
    l, r, k = 0, 0, 0
    for i in range(1, n): 
  
        # if i>R nothing matches so we will calculate. 
        # Z[i] using naive way. 
        if i > r: 
            l, r = i, i 
  
            # R-L = 0 in starting, so it will start 
            # checking from 0'th index. For example, 
            # for "ababab" and i = 1, the value of R 
            # remains 0 and Z[i] becomes 0. For string 
            # "aaaaaa" and i = 1, Z[i] and R become 5 
            while r < n and string[r - l] == string[r]: 
                r += 1
            z[i] = r - l 
            r -= 1
        else: 
  
            # k = i-L so k corresponds to number which 
            # matches in [L,R] interval. 
            k = i - l 
  
            # if Z[k] is less than remaining interval 
            # then Z[i] will be equal to Z[k]. 
            # For example, str = "ababab", i = 3, R = 5 
            # and L = 2 
            if z[k] < r - i + 1: 
                z[i] = z[k] 
  
            # For example str = "aaaaaa" and i = 2,  
            # R is 5, L is 0 
            else: 
  
                # else start from R and check manually 
                l = i 
                while r < n and string[r - l] == string[r]: 
                    r += 1
                z[i] = r - l 
                r -= 1

string = list(BXOR) + [-1] + list(AXOR) + list(AXOR)[:-1]
Z = [0 for i in range(len(string))]
getZarr(string, Z)
# print(string)
res = []
for i in range(N, len(string)):
    # print(i, Z[i])
    if (Z[i] >= N):
        # print(AXOR[0], BXOR[i-N-1])
        res.append((i - N - 1, AS[i-N-1] ^ BS[0]))
res.sort()
for a, b in res:
    print(a, b)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# (a,b,c,d) -> (ab,bc,cd,da) と変換
# xor x で不変量になる

N = int(readline())

A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

def convert(A):
    return [x ^ y for x,y in zip(A,A[1:])] + [A[-1] ^ A[0]]

C = convert(A); D = convert(B)

def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N=len(S)
    arr = [0]*N
    arr[0] = N
    i,j = 1,0
    while i<N:
        while i+j<N and S[j]==S[i+j]:
            j += 1
        arr[i]=j
        if not j:
            i += 1
            continue
        k = 1
        while i+k<N and k+arr[k]<j:
            arr[i+k] = arr[k]
            k += 1
        i += k; j -= k
    return arr

Z = Z_algorithm(D + [-1] + C + C)[N+1:N+N+1]

K = [i for i,x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k,x) for k,x in zip(K,X)))

Submission status: Runtime Error

Solution code:
# この方針かしこい

import os
import sys
import numpy as np

def z_algo(S):
    # Z-algoirhm  O(n)
    # Z[i] := S と S[i:] で prefix が何文字一致しているか
    # 検証: https://atcoder.jp/contests/arc055/submissions/14179788
    i, j, n = 1, 0, len(S)
    Z = np.zeros_like(S)
    Z[0] = n
    while i < n:
        while i+j < n and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        d = 1
        while i+d < n and d+Z[d] < j:
            Z[i+d] = Z[d]
            d += 1
        i += d
        j -= d
    return Z

def solve(N, A, B):
    Diff = np.empty(3*N, dtype=np.int64)
    Diff[0] = B[0] ^ B[-1]
    Diff[1:N] = B[1:] ^ B[:-1]
    Diff[N] = Diff[2*N] = A[0] ^ A[-1]
    Diff[N+1:2*N] = Diff[2*N+1:3*N] = A[1:] ^ A[:-1]
    Z = z_algo(Diff)[N:2*N]
    Ans = [(0,0)]*0
    for i in range(N):
        z = Z[i]
        if z >= N:
            Ans.append((i, B[0]^A[i]))
    return np.array(Ans)


# >>> numba compile >>>
numba_config = [
    [z_algo, "i8[:](i8[:])"],
    [solve, "i8[:,:](i8,i8[:],i8[:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    B = np.array(input().split(), dtype=np.int64)
    Ans = solve(N, A, B).tolist()
    print("\n".join(map(lambda x: " ".join(map(str, x)), Ans)))

main()

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
def f(k,x):
  for i in range(N):
    C=[A[(i+k)%N]^x]
  return C
import numpy as np
M=max(A+B)
Msup=2**(int(np.log2(M)+1))
for k in range(0,N):
  for x in range(0,Msup+1):
    if f(k,x)==B:
      print((k,"",x)