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: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N = inp()
K = 6
aa = inpl()
bb = inpl()


# In[]:
# N = 6
# K = 6
# aa = (0,1,3,7,6,4)
# bb = (1,5,4,6,2,3)

Abins = [""]*K
rAbins = [""]*K
for a in aa:
    for k in range(K):
        tmp = (a>>k)&1
        Abins[k]  += str(tmp)
        rAbins[k] += str(tmp^1)

Bbins = [""]*K
for a in bb:
    for k in range(K):
        Bbins[k] += str((a>>k)&1)


# print(Abins)
# print(rAbins)
# print(Bbins)


# In[]:
def match(A,B):
    mp = [0]*(N+1)
    mp[0] = -1
    j = -1
    for i in range(N):
        while j >= 0 and A[i] != A[j]:
            j = mp[j]
        j += 1
        mp[i+1] = j
    b = 0
    a = 0
    koho = set()
    # mp[0] = 0
    while b < 2*N:
        # print(a,b)
        if A[a] == B[b]:
            if a == N-1:
                a = mp[a+1]
                b += 1
                koho.add(b-N)
            else:
                a += 1
                b += 1
        else:
            a = mp[a] + 1
            b += 1
    return koho


# In[]:
kohos = []
for rA,A,B in zip(rAbins,Abins,Bbins):
    B = B*2
    koho = match(A,B) | match(rA,B)

    # print(A,B)
    # print(koho)

    kohos.append(koho)

all = kohos[0]
for koho in kohos[1:]:
    all &= koho


# In[]:
all = sorted(list(set([(-a)%N for a in all])))


for t in all:
    print(t,aa[-1]^bb[-1-t])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import math
import numpy as np

mx = math.floor(math.log2(max(max(a),max(b)))) + 1
mxv = 2**mx
dic = {}
lis = []
ssa = [format(i,'0'+ str(mx) + 'b') for i in a]
ssb = [format(i,'0'+ str(mx) + 'b') for i in b]
index = 0
if index < mx:
    sa = [int(i[index]) for i in ssa]
    sb = [int(i[index]) for i in ssb]
    num = 0
    while num < n:
        t = np.roll(sa, -num)
        if sum(t ^ sb) == n:
            #print(f"p{num}")
            dic[num] = mxv/2
        if sum(t ^ sb) == 0:
            #print(f"n{num}")
            dic[num] = 0
        num += 1
    index += 1
    mxv /= 2

while index < mx:
    sa = [int(i[index]) for i in ssa]
    sb = [int(i[index]) for i in ssb]
    for x in dic:
        t = np.roll(sa, -x)
        if sum(t ^ sb) == n:
            dic[x] += mxv/2
        elif sum(t ^ sb) == 0:
            continue
        else:
            dic.pop(x)
    index += 1
    mxv /= 2

for k,v  in dic.items():
    print(k,int(v))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))

a=a+a
lis=[[]for i in range(n)]
for i in range(n):
    for j in range(n):
        lis[i].append(a[i+j]^b[i])

for i in range(n):
    kano=True
    for j in range(n):
        if(lis[0][i]!=lis[j][i]):
            kano=False
            break
    if(kano):
        print(i,lis[0][i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import math
import numpy as np

mx = math.floor(math.log2(max(max(a),max(b)))) + 1

dic = {}
lis = []
ssa = [format(i,'0'+ str(mx) + 'b') for i in a]
ssb = [format(i,'0'+ str(mx) + 'b') for i in b]
index = 0
if index < mx:
    sa = [int(i[index]) for i in ssa]
    sb = [int(i[index]) for i in ssb]
    num = 0
    while num < n:
        t = np.roll(sa, -num)
        if sum(t ^ sb) == n:
            #print(f"p{num}")
            dic[num] = 2**(mx-index-1)
        if sum(t ^ sb) == 0:
            #print(f"n{num}")
            dic[num] = 0
        num += 1
    index += 1

while index < mx:
    sa = [int(i[index]) for i in ssa]
    sb = [int(i[index]) for i in ssb]
    for x in dic:
        t = np.roll(sa, -x)
        if sum(t ^ sb) == n:
            dic[x] += 2**(mx-index-1)
        elif sum(t ^ sb) == 0:
            continue
        else:
            dic.pop(x)
    index += 1

for k,v  in dic.items():
    print(k,int(v))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if len(set(a)) == len(set(b)) == 1:
    x = a[0]^b[0]
    for i in range(n):
        print(i, x)
else:
    a += a
    for i in range(n):
        start = a[i]^b[0]
        f = True
        for j in range(n):
            if start != a[i+j]^b[j]:
                f = False
                break
        if f:
            print(i, start)

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
N = int(input())
a = inpl()
b = inpl()

da = [a[i-1]^a[i] for i in range(N)]
db = [b[i-1]^b[i] for i in range(N)]
ans = []
for k in range(N):
    for i in range(N):
        if da[(i+k)%N] != db[i]:
            break
    else:
        ans.append((k,a[k]^b[0]))
for k, x in ans:
    print(k,x)

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*30:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*50:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for k in range(N):
    x = B[0] ^ A[k]
    for i,b in enumerate(B):
        if b != A[(i+k)%N] ^ x:
            break
    else:
        print(k,x)

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*100:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    for k in range(n):
        hyp = b[0]^a[k]
        judge = True
        for _ in [0]*500:
            w = random.randrange(n)
            if b[w] != a[(w+k)%n]^hyp:
                judge = False
                break
        if judge:
            print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import math
import numpy as np

mx = math.floor(math.log2(max(max(a),max(b)))) + 1

dic = {}
lis = []
mx = 2 ** mx
if mx >= 2:
    sa = [int(i % mx // (mx/2)) for i in a]
    sb = [int(i % mx // (mx/2)) for i in b]
    num = 0
    while num < n:
        t = np.roll(sa, -num)
        if sum(t ^ sb) == n:
            #print(f"p{num}")
            dic[num] = mx/2
        if sum(t ^ sb) == 0:
            #print(f"n{num}")
            dic[num] = 0
        num += 1
    mx /= 2

while mx >= 2:
    sa = [int(i % mx // (mx/2)) for i in a]
    sb = [int(i % mx // (mx/2)) for i in b]
    for x in dic:
        t = np.roll(sa, -x)
        if sum(t ^ sb) == n:
            dic[x] += mx/2
        elif sum(t ^ sb) == 0:
            continue
        else:
            dic.pop(x)
    mx /= 2

for k,v  in dic.items():
    print(k,int(v))

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*300:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge:
                print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*500:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge:
                print(k,hyp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import math
import numpy as np

mx = math.floor(math.log2(max(max(a),max(b)))) + 1
pos = []
neg = []

dic = {}
lis = []
if mx >= 1:
    sa = [i % 2**mx // 2**(mx-1) for i in a]
    sb = [i % 2**mx // 2**(mx-1) for i in b]
    num = 0
    while num < n:
        t = np.roll(sa, -num)
        if sum(t ^ sb) == n:
            #print(f"p{num}")
            dic[num] = 2**(mx-1)
        if sum(t ^ sb) == 0:
            #print(f"n{num}")
            dic[num] = 0
        num += 1
    mx -= 1

while mx >= 1:
    sa = [i % 2**mx // 2**(mx-1) for i in a]
    sb = [i % 2**mx // 2**(mx-1) for i in b]
    for x in dic:
        t = np.roll(sa, -x)
        if sum(t ^ sb) == n:
            dic[x] += 2**(mx-1)
        elif sum(t ^ sb) == 0:
            continue
        else:
            dic.pop(x)
    mx -= 1

for k,v  in dic.items():
    print(k,v)

Submission status: Time Limit Exceeded

Solution code:

base = 1234
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 = set(range(N))
for k in range(30):
    tmp = set()
    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:
            tmp.add(i)
        if a_hash_r == b_hash:
            tmp.add(i)
        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
    ans&=tmp
ans = sorted(list(ans))
for k in ans:
    x = a[k]^b[0]
    print(k, x)

Submission status: Time Limit Exceeded

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


def main():
    n = int(input())
    
    a = list(map(int,input().split()))
    b = list(map(int,input().split()))

    p = 0
    q = 0
    for eA,eB in zip(a,b):
        p = (p+eA)<<30
        q = (q+eB)<<30
    p = p>>30
    q = q>>30


    for k in range(n):
        hyp = b[0]^a[k]
        judge = p^q
        if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
            print(k,hyp)
        q = (q>>30) + (b[n-1-k]<<(30*(n-1)))

    





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import random
N=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
#N=2*10**5
#a=[random.randrange(2**30) for i in range(N)]
#b=[random.randrange(2**30) for i in range(N)]

for k in range(N):
    x=a[k]^b[0]
    flag=1
    for line in range(1000):
        i=random.randrange(N)
        if a[(k+i)%N]^b[i]!=x:
            flag=0
            break
    if flag==1:
        print(k,x)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

class Compress:

    def __init__(self, vs):
        self.xs = list(set(vs))
        self.xs.sort()

    def compress(self, x):
        return bisect_left(self.xs, x)

    def decompress(self, i):
        return self.xs[i]

def suffix_array(s):
    n = len(s)
    comp = Compress(s)
    t = [comp.compress(s[i]) for i in range(n)]
    cnt = [0] * n
    for i in range(n):
        cnt[t[i]] += 1
    for i in range(1, n):
        cnt[i] += cnt[i-1]
    p = [0] * n
    for i in range(n):
        cnt[t[i]] -= 1
        p[cnt[t[i]]] = i
    c = [0] * n
    cl = 0
    for i in range(1, n):
        if s[p[i]] != s[p[i-1]]:
            cl += 1
        c[p[i]] = cl

    pn = [0] * n
    cn = [0] * n
    h = 0
    while (1 << h) < n:
        for i in range(n):
            pn[i] = p[i] - (1 << h)
            if pn[i] < 0:
                pn[i] += n
        cnt = [0] * n
        for i in range(n):
            cnt[c[pn[i]]] += 1
        for i in range(1, n):
            cnt[i] += cnt[i-1]
        for i in range(n)[::-1]:
            cnt[c[pn[i]]] -= 1
            p[cnt[c[pn[i]]]] = pn[i]
        cn[p[0]] = 0
        cl = 0
        for i in range(1, n):
            cur = (c[p[i]], c[(p[i] + (1 << h)) % n])
            prev = (c[p[i-1]], c[(p[i-1] + (1 << h)) % n])
            if cur != prev:
                cl += 1
            cn[p[i]] = cl
        c, cn = cn, c
        h += 1
    return p


def bin_search(a, b, sa, lower):
    lb, ub = -1, N
    while ub - lb > 1:
        m = (lb + ub) // 2
        for i in range(N):
            j = (sa[m] + i) % N
            if a[i] < b[j]:
                ub = m
                break
            if a[i] > b[j]:
                lb = m
                break
        else:
            if lower:
                ub = m
            else:
                lb = m
    return ub

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [a[i] ^ a[(i+1)%N] for i in range(N)]
d = [b[i] ^ b[(i+1)%N] for i in range(N)]
sa = suffix_array(d)
lb = bin_search(c, d, sa, True)
ub = bin_search(c, d, sa, False)
ans = []
for j in range(lb, ub):
    k = (N - sa[j]) % N
    x = a[k] ^ b[0]
    ans.append((k, x))
ans.sort()
for k, x in ans:
    print(k, x)

Submission status: Accepted

Solution code:
import re

N = int(input())
A = list(map(lambda x: bin(int(x))[2:], input().split()))
B = list(map(lambda x: bin(int(x))[2:], input().split()))
keta = max(max(map(len, A)), max(map(len, B)))


def xor(a, b):
    while keta > len(b):
        b = '0' + b
    while keta > len(a):
        a = '0' + a
    ret = ''
    for a_, b_ in zip(a, b):
        ret += '0' if a_ == b_ else '1'
    return ret


def create_table(pattern):
    table = [0 for _ in range(len(pattern)+1)]
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
        else:
            table[i] = j
            j = 0
    table[i+1] = j
    return table


def kmp_search(string, pattern):
    ret = []
    table = create_table(pattern)
    i = j = 0
    while i < len(string):
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j == 0:
            i += 1
        else:
            j = table[j]
        if j == len(pattern):
            ret.append(i - j)
            j = table[j]
    else:
        return ret

def bm_search(string, pattern):
    ret = []
    pat_len = len(pattern)
    skip = [pat_len for _ in range(256)]
    for i in range(pat_len):
        skip[ord(pattern[i])] = pat_len - i - 1
    i = pat_len - 1
    while i < len(string):
        j = pat_len - 1
        while string[i] == pattern[j]:
            if j == 0:
                ret.append(i)
            i -= 1
            j -= 1
        i = i + max(skip[ord(string[i])], pat_len-j)
    return ret


C, D = [], []
for i in range(N-1):
    C.append(xor(A[i], A[i+1]))
    D.append(xor(B[i], B[i + 1]))
C.append(xor(A[-1], A[0]))
D.append(xor(B[-1], B[0]))
for k in kmp_search(D + D, C)[::-1]:
    if k == 0:
        continue
    print(N-k, int(xor(A[N-k], B[0]), 2))

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
a = LI()
b = LI()

if N == 1:
    print(0,a[0]^b[0])
    exit()

A = [a[i] ^ a[i+1] for i in range(N-1)]
A = A + [a[N-1] ^ a[0]] + A
B = [b[i] ^ b[i+1] for i in range(N-1)]

# Aの長さN-1の連続部分列の中で、Bと一致するものは存在するか
# Rolling Hash


def f(mod,base):
    x = pow(base,N-1,mod)  # x = base**(N-1)

    d = 0  # Bのhash値
    for i in range(N-1):
        d *= base
        d += B[i]
        d %= mod

    c = 0  # Aの左N-1文字のhash値
    for i in range(N-1):
        c *= base
        c += A[i]
        c %= mod

    for i in range(N):
        if c == d:
            print(i,a[i] ^ b[0])
        c *= base
        c -= A[i]*x
        c += A[i+N-1]
        c %= mod


f(10**9+7,1234)

Submission status: Accepted

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

def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    mod=10**9+7
    """
    kを決めるかxを決めるか，
    kを決めればxが一意に決まり，N個試してO(N^2)
    xを決めればどうなるんだろう．
    ai全部にxorして，それをずらせばbになるならok．なんかもう少しうまくできそう．
    
    解説読んだ.
    全部のところに同じ操作をしている=>2箇所を使うことでうまく追加分を打ち消すことを考える．
    隣接2箇所を選びxorすれば xor xの部分が消える（もし+xなら2箇所選んで引けば良いというお話）
    
    shiftしたものが一致するか知る方法=>aとbなら，a*2の中にbがあるか探す．ここでKMP法やz-algoritmを使う
    
    
    """
    
    def Z(s):
        n=len(s)
        lcp=[0]*n
        lcp[0]=n
        L,R=0,0
        for i in range(1,n):
            if(i>=R): # 過去の結果の再利用が不可
                L=i
                R=i
                while(R<n and s[R-L]==s[R]):
                    R+=1
                lcp[i]=R-L
            elif(lcp[i-L]<R-i): # 過去の結果を再利用
                lcp[i]=lcp[i-L]
            else: # 過去の結果を一部再利用
                L=i
                while(R<n and s[R-L]==s[R]):
                    R+=1
                lcp[i]=R-L
        return lcp
    
    N=I()
    a=LI()
    b=LI()
    a+=[a[0]]
    b+=[b[0]]
    
    #隣接二項のxorがrotateしてることが必要
    a2=[0]*N
    b2=[0]*N
    for i in range(N):
        a2[i]=a[i+1]^a[i]
        b2[i]=b[i+1]^b[i]
        
    #a2*2の中にb2があるか見たい，abbに対してZしてi>=Nで，LCPがN以上の場所
    
    K=[]
    abb=a2+b2+b2
    L=Z(abb)
    
    for i in range(N,2*N,1):
        if L[i]>=N:
            K.append((2*N-i)%N)
            
    X=[]
    for k in K:
        x=b[0]^a[k]
        X.append(x)
    
    if K!=[]:
        K,X=zip(*sorted(zip(K,X)))
    else:
        exit()
        
    for i in range(len(K)):
        print(K[i],X[i])
        

    

main()

Submission status: Accepted

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]))
    if len(Ans):
        return np.array(Ans)
    return np.zeros((0, 2), dtype=np.int64)


# >>> 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()
    for k, x in Ans:
        print(f"{k} {x}")

main()

Submission status: Accepted

Solution code:
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 = [0] * n
    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


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_diff = []
a2 = A[-1]
for a in A:
    A_diff.append(a^a2)
    a2 = a
B_diff = []
b2 = B[-1]
for b in B:
    B_diff.append(b^b2)
    b2 = b
A_diff_2 = A_diff + A_diff[:-1]
Z = z_algo(A_diff_2)
A_diff_str = "_".join(map(str, A_diff_2))
B_diff_str = "_".join(map(str, B_diff))
idx = A_diff_str.find(B_diff_str)
if idx==-1:
    exit()
idx = A_diff_str[:idx].count("_")
Ans = []
b0 = B[-idx]
for i, (z, a, b) in enumerate(zip(Z, A, B)):
    if z >= N:
        Ans.append([(idx+i)%N, a^b0])
        # x = [idx, i, a, b, B[-idx]]
        # print(x)
Ans.sort()  # これいる？
for k, x in Ans:
    print(f"{k} {x}")

Submission status: Accepted

Solution code:
LI = lambda: list(map(int, input().split()))

N = int(input())
A = LI()
B = LI()


def main():
    s = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    t = [B[i] ^ B[(i + 1) % N] for i in range(N)] * 2
    w = [0] * N
    for i in range(1, N):
        j = w[i - 1]
        while j != 0 and s[i] != s[j]:
            j = w[j - 1]
        if s[i] == s[j]:
            w[i] = j + 1
        else:
            w[i] = 0

    k_list = []
    i, j = 0, 0
    while i < N:
        while j < N and t[i + j] == s[j]:
            j += 1
        if j == N:
            k_list.append(-i % N)
        if j == 0:
            i += 1
        else:
            i += j - w[j - 1]
    
    k_list.sort()
    for k in k_list:
        x = A[k] ^ B[0]
        print(k, x)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

class RollingHash(object):
    """
        construct: O(N)
        query:
            hash: O(1)
            lcp: O(logN)
            search: O(N)
    """
    __base1 = 1007;
    __mod1 = 10 ** 9
    __base2 = 1009;
    __mod2 = 10 ** 7

    def __init__(self, s):
        n = len(s)
        self.__s = s
        self.__n = n
        b1 = self.__base1;
        m1 = self.__mod1
        b2 = self.__base2;
        m2 = self.__mod2
        H1, H2 = [0] * (n + 1), [0] * (n + 1)
        P1, P2 = [1] * (n + 1), [1] * (n + 1)
        for i in range(n):
            H1[i + 1] = (H1[i] * b1 + (s[i])) % m1
            H2[i + 1] = (H2[i] * b2 + (s[i])) % m2
            P1[i + 1] = P1[i] * b1 % m1
            P2[i + 1] = P2[i] * b2 % m2
        self.__H1 = H1
        self.__H2 = H2
        self.__P1 = P1
        self.__P2 = P2

    @property
    def str(self):
        return self.__s

    @property
    def len(self):
        return self.__n

    def hash(self, l, r=None):
        """
            l,r: int (0<=l<=r<=n)
            return (hash1,hash2) of S[l:r]
        """
        m1 = self.__mod1
        m2 = self.__mod2
        if r is None: r = self.__n
        assert 0 <= l <= r <= self.__n
        hash1 = (self.__H1[r] - self.__P1[r - l] * self.__H1[l] % m1) % m1
        hash2 = (self.__H2[r] - self.__P2[r - l] * self.__H2[l] % m2) % m2
        return hash1, hash2

    @classmethod
    def lcp(cls, rh1, rh2, l1, l2, r1=None, r2=None):
        """
            rh1,rh2: RollingHash object
            l1,l2,r1,r2: int 0<=l1<=r1<=r1.len, 0<=l2<=r2<=rh2.len
            return lcp length between rh1[l1:r1] and rh2[l2:r2]
        """
        if r1 is None: r1 = rh1.__n
        if r2 is None: r2 = rh2.__n
        assert 0 <= l1 <= r1 <= rh1.__n and 0 <= l2 <= r2 <= rh2.__n
        L = 0
        R = min(r1 - l1, r2 - l2)
        if rh1.hash(l1, l1 + R) == rh2.hash(l2, l2 + R): return R
        while R - L > 1:
            H = (L + R) // 2
            if rh1.hash(l1, l1 + H) == rh2.hash(l2, l2 + H): L = H
        else:
            R = H
        return L

    @classmethod
    def search(cls, pattern, text):
        """
        pattern,text: RollingHash object
        return list of index i's satisfying text[i:] starts with pattern
        """
        n = text.__n;
        m = pattern.__n
        res = []
        for i in range(n - m + 1):
            if text.hash(i, i + m) == pattern.hash(0, m):
                res.append(i)
        return res


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

    dA = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    dB = [B[i] ^ B[(i + 1) % N] for i in range(N)]

    dA += dA
    # 今回は数字を扱うのでRollingHash: init() ord削除し対応
    RHa = RollingHash(dA)
    RHb = RollingHash(dB)
    query = RHb.hash(0, N - 1)
    ans = []
    for i in range(N):
        val = RHa.hash(i, i + N - 1)
        if val == query:
            ans.append((i, A[i] ^ B[0]))
    ans.sort()
    for k, x in ans:
        print(k, x)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

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

    dA = [A[i] ^ A[(i + 1) % N] for i in range(N)]
    dB = [B[i] ^ B[(i + 1) % N] for i in range(N)]

    dA = dA + dA[:-1]
    # C string D pattern
    K = KMP(dB).search(dA)
    for k in K:
        print(k, A[k] ^ B[0])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
C = [0]*(3*n)
for i in range(n):
  C[i] = B[i]^B[(i+1)%n]
  C[i+n] = A[i]^A[(i+1)%n]
  C[i+n+n] = C[i+n]

def z_algo(S):
    N = len(S)
    A = [0]*N
    A[0] = N
    i, j = 1, 0
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        A[i] = j
        if not j:
            i += 1
            continue
        k = 1
        while i+k < N and k+A[k] < j:
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    return A  

P = z_algo(C)
for i, p in enumerate(P[n:n+n]):
  if p >= n:
    x = A[i]^B[0]
    print(i, x)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2**89-1
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    a = LI()
    b = LI()

    ax = []
    bx = []
    for i in range(N):
        ax.append(a[i-1] ^ a[i])
        bx.append(b[i-1] ^ b[i])

    az = 0
    bz = 0
    m = 2**30
    for i in range(N):
        az = (az * m + ax[i]) % MOD
        bz = (bz * m + bx[i]) % MOD

    for i in range(N):
        if az == bz:
            print(i,a[i] ^ b[0])
        az = ((az - ax[i] * pow(m,N-1,MOD)) * m + ax[i]) % MOD

if __name__ == '__main__':
    main()