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

def KMP(sentence,word):
  ret=[]
  
  def make_table(word):
    n=len(word)
    table=[0]*(n+1)
    table[0]=-1
    j=-1
    for i in range(n):
      while j>=0 and word[i]!=word[j]:
        j=table[j]
      j+=1
      table[i+1]=j
    return table
  
  table=make_table(word)
  sentence_size=len(sentence)
  word_size=len(word)
  m=0
  i=0
  while m+i<sentence_size:
    if word[i]==sentence[m+i]:
      i+=1
      if i==word_size:
        ret.append(m)
        m=m+i-table[i]
        i=table[i]
    else:
      m=m+i-table[i]
      if i>0:
        i=table[i]
  return ret

n=int(input())
arr1=list(map(int,input().split()))
arr2=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
  a.append(arr1[i]^arr1[(i+1)%n])
  b.append(arr2[i]^arr2[(i+1)%n])
a=(a+a)[:-1]
ks=KMP(a,b)
if len(ks)==0:
  exit()
ans=[]
for k in ks:
  ans.append((k,arr2[0]^arr1[k%n]))
ans=sorted(ans,key=lambda x:x[1])
ans=sorted(ans,key=lambda x:x[0])
for k,x in ans:
  print(k,x)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
da = []
db = []
for i in range(n-1):
    da.append(A[i+1] ^ A[i])
    db.append(B[i+1] ^ B[i])
da.append(A[-1]^A[0])
db.append(B[-1]^B[0])
    
import random
M = 10**9+7
b = random.choice(range(M))
def rhash(s):
    import random
    ans = 0
    v = 1
    for item in s:
        ans += item*v
        v *= b
        ans %= M
        v %= M
    return ans

h = rhash(db)
g = rhash(da)
t = pow(b, n, M)
ans = []
for i in range(n):
    if h==g:
#         if all(da[(j+i)%n]==db[j] for j in range(n)):
        ans.append((i,A[i]^B[0]))
    h *= b
    h = h - t*db[n-1-i] + db[n-1-i]
    h %= M
    
write("\n".join(" ".join(map(str, item)) for item in ans))

Submission status: Accepted

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


def bit_most(v):
    # 最高位の桁を得る
    if v == 0:
        return 0
    else:
        return len(bin(v))-2


def z_algorithm(S):
    """Zアルゴリズム
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = N
    return Z


def solve(N: int, a: "List[int]", b: "List[int]"):

    a1 = [0]*(2*N)
    b1 = [0]*N
    b2 = [0]*N
    k_cand = [True]*N
    for keta in range(bit_most(max(max(a), max(b)))+1):
        for i, aa in enumerate(a):
            a1[i] = a1[i+N] = (aa >> keta) & 1
        for i, bb in enumerate(b):
            b1[i] = v = (bb >> keta) & 1
            b2[i] = 1-v
        Z1 = z_algorithm(b1 + [-1] + a1)
        Z2 = z_algorithm(b2 + [-1] + a1)
        # print(a1+[-1]+b1)
        # print(a1+[-1]+b2)
        # print("Z1", Z1)
        # print("Z2", Z2)
        for i in range(N):
            if k_cand[i]:
                k_cand[i] = Z2[i+N+1] == N or Z1[i+N+1] == N
        # print(k_cand)

    for i in range(N):
        if k_cand[i]:
            print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def z_algorithm(S):
    """Zアルゴリズム
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = N
    return Z


def solve(N: int, a: "List[int]", b: "List[int]"):

    a1 = [0]*(2*N)
    b1 = [0]*N
    b2 = [0]*N
    k_cand = [True]*N
    for keta in range(30):
        for i, aa in enumerate(a):
            a1[i] = a1[i+N] = (aa >> keta) & 1
        for i, bb in enumerate(b):
            b1[i] = v = (bb >> keta) & 1
            b2[i] = 1-v
        Z1 = z_algorithm(b1 + [-1] + a1)
        Z2 = z_algorithm(b2 + [-1] + a1)
        # print(a1+[-1]+b1)
        # print(a1+[-1]+b2)
        # print("Z1", Z1)
        # print("Z2", Z2)
        for i in range(N):
            if k_cand[i]:
                k_cand[i] = Z2[i+N+1] == N or Z1[i+N+1] == N
        # print(k_cand)

    for i in range(N):
        if k_cand[i]:
            print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


# https://tjkendev.github.io/procon-library/python/string/rolling_hash.html

base = 37
mod = 10**9 + 9
pw = None


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


def setup_pw(l):
    global pw
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod


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


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    a1 = [0]*N
    a2 = [0]*N
    b1 = [0]*(2*N)
    k_cand = [True]*N
    setup_pw(2*N)
    # 周期性を考慮すべきだが、二週分をとっていないのは何で対応しているのか
    # 一致パターンと、真逆パターンがあるはずだが、どこで見ているのか
    for keta in range(30):
        mask = 1 << keta
        for i, aa in enumerate(a):
            a1[i] = (aa & mask) >> keta
            a2[i] = (~aa & mask) >> keta
        for i, bb in enumerate(b):
            b1[i] = (bb & mask) >> keta
            b1[i+N] = (bb & mask) >> keta
        P = rolling_hash(a1)
        Q = rolling_hash(a2)
        R = rolling_hash(b1)
        for i in range(N):
            if k_cand[i]:
                if not ((get(P, 0, N) == get(R, i, i+N)) or
                        (get(Q, 0, N) == get(R, i, i+N))):
                    k_cand[i] = False
        # k_cand1 = zfindall(b1, a1, separator=[-1])
        # k_cand2 = zfindall(b1, a2, separator=[-1])
        # for i in range(N):
        #     k_cand[i] = k_cand[i] & ((i in k_cand1) or (i in k_cand2))

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] == True:
        print(0, b[0] ^ a[0])
        for i, k in enumerate(k_cand[:0:-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    else:
        for i, k in enumerate(k_cand[::-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


B = 10**7+7
MOD = 10**9+7

# 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


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return {i-N-1 for i in range(len(conc)) if Z[i] == N}


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    a1 = [0]*N
    a2 = [0]*N
    b1 = [0]*(2*N)
    k_cand = [True]*N
    for keta in range(30):
        mask = 1 << keta
        for i, aa in enumerate(a):
            a1[i] = (aa & mask) >> keta
            a2[i] = (~aa & mask) >> keta
        for i, bb in enumerate(b):
            b1[i] = (bb & mask) >> keta
            b1[i+N] = (bb & mask) >> keta
        P = RollingHash(a1, 97, MOD)
        Q = RollingHash(a2, 97, MOD)
        R = RollingHash(b1, 97, MOD)
        for i in range(N):
            if k_cand[i]:
                if not ((P.get(0, N) == R.get(i, i+N)) or
                        (Q.get(0, N) == R.get(i, i+N))):
                    k_cand[i] = False
        # k_cand1 = zfindall(b1, a1, separator=[-1])
        # k_cand2 = zfindall(b1, a2, separator=[-1])
        # for i in range(N):
        #     k_cand[i] = k_cand[i] & ((i in k_cand1) or (i in k_cand2))

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] == True:
        print(0, b[0] ^ a[0])
        for i, k in enumerate(k_cand[:0:-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    else:
        for i, k in enumerate(k_cand[::-1], start=1):
            if k:
                print(i, b[0] ^ a[i])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


B = 10**7+7
MOD = 10**9+7


def z_algorithm(S):
    """Zアルゴリズム
    https://snuke.hatenablog.com/entry/2014/12/03/214243 の二番目のコード
    """
    N = len(S)
    Z = [0]*N

    c = 0
    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
    Z[0] = len(S)
    return Z


def zfindall(text, pattern, separator="$"):
    """テキストからパターンと一致する部分文字列を探す。
    開始インデックスを返す
    Zアルゴリズムを利用する
    """
    N = len(pattern)
    conc = pattern+separator+text
    Z = z_algorithm(conc)
    return [i-N-1 for i in range(len(conc)) if Z[i] == N]


def solve(N: int, a: "List[int]", b: "List[int]"):

    c = [a[i] ^ a[(i+1) % N]for i in range(N)]
    d = [b[i] ^ b[(i+1) % N]for i in range(N)]*2
    i = -1
    k_cand = zfindall(d, c, separator=[-1])
    # print(k_cand)

    ans = []
    if len(k_cand) == 0:
        return
    if k_cand[0] % N == 0:
        print(0, b[0] ^ a[0])
        for k in k_cand[:0:-1]:
            if k < N:
                print(-k % N, b[0] ^ a[-k % N])
    else:
        for k in k_cand[::-1]:
            if k < N:
                print(-k % N, b[0] ^ a[-k % N])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    b = [int(next(tokens)) for _ in range(N - 1 - 0 + 1)]  # type: "List[int]"
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

X = []
for a,b in zip(A,A[1:]):
    X.append(a ^ b)
X.append(A[-1] ^ A[0])

Y = []
for a,b in zip(B,B[1:]):
    Y.append(a ^ b)
Y.append(B[-1] ^ B[0])

def z_algorithm(s):
    N = len(s)
    ret = [0]*N
    ret[0] = N
    i,j = 1,0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        ret[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + ret[k]<j:
            ret[i+k] = ret[k]
            k += 1
        i += k
        j -= k
    return ret

za = z_algorithm(X + [-1] + Y + Y)
for i in range(N):
    if za[-N-i] == N:
        print(i, A[i]^B[0])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a+=a
b=list(map(int,input().split()))
aa=[a[i-1]^a[i] for i in range(1,n*2)]
bb=[b[i-1]^b[i] for i in range(1,n)]
s=bb+aa
from random import randint
roli_mod=1370757747362922367
roli_r=1#randint(2,roli_mod-2)
roli_table=[0]
roli_rr=1
for i in range(3*(n-1)):
  roli_table.append((roli_table[-1]+roli_rr*s[i])%roli_mod)
  roli_rr*=roli_r
  roli_rr%=roli_mod
def roli_hash(i,j):return ((roli_table[j+1]-roli_table[i]+roli_mod)%roli_mod)*pow(roli_r,roli_mod-1-i,roli_mod)%roli_mod
def roli_check(i1,j1,i2,j2):return roli_hash(i1,j1)==roli_hash(i2,j2)
ans=[]
for k in range(n-1,2*(n-1)+1):
  if roli_check(0,n-2,k,k+(n-1)-1):
    ans.append(k-(n-1))
for i in ans:
  print(i,a[i]^b[0])

Submission status: Accepted

Solution code:
def main():
    def z_algo(S):
        n, i, j = len(S), 1, 0
        a = [0]*n
        a[0] = n
        while i < n:
            while i+j < n and S[i+j] == S[j]:
                j += 1
            if not j:
                i += 1
                continue
            a[i], k = j, 1
            while a[k] < j-k and i+k < n:
                a[i+k] = a[k]
                k += 1
            i += k
            j -= k
        return a

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    a1 = [a[i-1] ^ a[i] for i in range(n)]
    z = z_algo([b[i-1] ^ b[i] for i in range(n)]+a1+a1)
    memo = []
    for i in range(n):
        if z[n+i] >= n:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        print(i, b0 ^ a[i])


main()

Submission status: Accepted

Solution code:
def main():
    mod, pow3, pow3i, p = 2**61-1, [1]*400001, [1]*200001, 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 400001):
        pow3[i] = p = p*3 % mod
    p = 1
    for i in range(1, 200001):
        pow3i[i] = p = p*i3 % mod

    class rolling_hash():
        def __init__(self, seq, char_list=None):
            seq_size = self.seq_size = len(seq)  # 文字列の長さ
            mod = self.mod = 2**61-1  # mod
            Hash = self.Hash = [0]*(seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(seq_size):
                Hash[i+1] = (Hash[i] + (seq[i]+1) * pow3[i]) % mod

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash[r]-self.Hash[l])*pow3i[l] % self.mod)

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    memo = []

    a1 = rolling_hash([a[i-1] ^ a[i] for i in range(n)] +
                      [a[i-1] ^ a[i] for i in range(n)])
    b_hash = rolling_hash([b[i-1] ^ b[i] for i in range(n)]).calc_hash(0, n)
    for i in range(n):
        if a1.calc_hash(i, i+n) == b_hash:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        x = b0 ^ a[i]
        print(i, x)


main()

Submission status: Accepted

Solution code:
def main():
    mod, pow3, p = 2**31-1, [1]*200001, 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        pow3[i] = p = p*3 % mod

    def rolling_hash(seq):
        h = sum([(i+1)*j for i, j in zip(seq, pow3[:-1])]) % mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    n = int(input())
    a, b = list(map(int, input().split())), list(map(int, input().split()))
    pn, memo = pow3[n], []

    a1 = [a[i-1] ^ a[i] for i in range(n)]
    b1 = [b[i-1] ^ b[i] for i in range(n)]
    b_hash = sum([(i+1)*j for i, j in zip(b1, pow3[:-1])]) % mod
    A1 = rolling_hash(a1)
    for i, j in enumerate(A1):
        if j == b_hash:
            memo.append(i)
    b0 = b[0]
    for i in memo:
        x = b0 ^ a[i]
        print(i, x)


main()

Submission status: Accepted

Solution code:
def main():
    mod = 2**31-1
    pow3 = [1]*200001
    p = 1
    i3 = pow(3, mod-2, mod)
    for i in range(1, 200001):
        p = p*3 % mod
        pow3[i] = p

    def rolling_hash(seq):
        h = 0
        for i, j in enumerate(seq):
            h += (j+1)*pow3[i]
        h %= mod
        H0s = [0]*n
        for i, j in enumerate(seq):
            H0s[i] = h
            h = (h-j-1+(j+1)*pn)*i3 % mod
        return H0s

    def rolling_hash2(seq):
        p = 0
        p2 = 0
        for i, j in enumerate(seq):
            p += (j+1)*pow3[i]
            p2 += (2-j)*pow3[i]
        return p % mod, p2 % mod

    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    m = max(a+b)
    a1 = [0]*n
    b1 = [0]*n
    memo = [0]*n
    cnt = n
    pn = pow3[n]

    for k in range(len(bin(m))-2):
        k2 = 2**k
        for i, j in enumerate(a):
            a1[i] = (j & k2) >> k
        for i, j in enumerate(b):
            b1[i] = (j & k2) >> k
        b_hash, b_hash2 = rolling_hash2(b1)
        A1 = rolling_hash(a1)
        for i, (j, k) in enumerate(zip(memo, A1)):
            if j is None:
                continue
            elif k == b_hash:
                pass
            elif k == b_hash2:
                memo[i] += k2
            else:
                memo[i] = None
                cnt -= 1
        if cnt == 0:
            return

    for i, j in enumerate(memo):
        if j is not None:
            print(i, j)


main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = [0] * n
d = [0] * (2 * n - 1)
for i in range(n - 1):
    c[i] = b[i] ^ b[i + 1]
    d[i] = a[i] ^ a[i + 1]
c[n - 1] = b[0] ^ b[-1]
d[n - 1] = a[0] ^ a[-1]
for i in range(n - 1):
    d[n + i] = d[i]
t = [0] * (n + 1)
t[0] = -1
j = -1
for i in range(n):
    while j >= 0 and c[i] != c[j]:
        j = t[j]
    j += 1
    t[i + 1] = j
m = 0
i = 0
ans = []
while m < n:
    if c[i] == d[m + i]:
        i += 1
        if i == n:
            ans.append(m)
            m += i - t[i]
            i = t[i]
    else:
        m += i - t[i]
        if i > 0:
            i = t[i]
for k in ans:
    print(k, a[k] ^ b[0])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

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

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

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


def slv(N, A, B):
    a = []
    for i in range(N):
        a.append(A[i]^A[i-1])
    a = a[:] + a[:]
    b = []
    for i in range(N):
        b.append(B[i]^B[i-1])

    ah = RollingHash(a)
    bh = RollingHash(b)

    ans = []
    h = bh.calc(0, N)
    for k in range(N):
        if ah.calc(k, N+k) == h:
            ans.append('%d %d' % (k, A[k]^B[0]))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

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

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

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


def slv(N, A, B):
    a = []
    for i in range(N):
        a.append(A[i]^A[i-1])
    b = []
    for i in range(N):
        b.append(B[i]^B[i-1])

    ah = RollingHash(a)
    bh = RollingHash(b)

    ans = []
    for k in range(N):
        if ah.calc(k, N) == bh.calc(0, N-k) and ah.calc(0, k) == bh.calc(N-k, N):
            ans.append('%d %d' % (k, A[k]^B[0]))


    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

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

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

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


def slv(N, A, B):
    a = []
    for i in range(N):
        a.append(A[i]^A[i-1])
    b = []
    for i in range(N):
        b.append(B[i]^B[i-1])
    b = b[:] + b[:]

    ah = RollingHash(a, num=1)
    bh = RollingHash(b, num=1)

    h = ah.calc(0, N)
    ans = []
    for k in range(N):
        if bh.calc(N-k, N-k+N) == h:
            ans.append('%d %d' % (k, A[0]^B[(N-k)%N]))


    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


class RollingHash():
    """
    Original code is https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
    """
    class RH():
        def __init__(self, s, base, mod):
            self.base = base
            self.mod = mod
            self.rev = pow(base, mod-2, mod)

            l = len(s)
            self.h = h = [0]*(l+1)
            tmp = 0
            for i in range(l):
                num = s[i]
                tmp = (tmp*base + num) % mod
                h[i+1] = tmp

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

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

    @staticmethod
    def gen(a, b, num):
        result = set()
        while 1:
            import random
            import math
            random.seed()
            while 1:
                v = random.randint(a, b)//2*2+1
                if v not in result:
                    break
            for x in range(3, int(math.sqrt(v))+1, 2):
                if v % x == 0:
                    break
            else:
                result.add(v)
                if len(result) == num:
                    break
        return result

    def __init__(self, s, rand=False, num=5):
        if rand:
            bases = RollingHash.gen(2, 10**3, num)
        else:
            assert num <= 10
            bases = [641, 103, 661, 293, 547, 311, 29, 457, 613, 599][:num]

        MOD = 10**9+7
        self.rhs = [self.RH(s, b, MOD) for b in bases]

    def calc(self, l, r):
        return tuple(rh.calc(l, r) for rh in self.rhs)


def slv(N, A, B):
    a = []
    for i in range(N):
        a.append(A[i]^A[i-1])
    b = []
    for i in range(N):
        b.append(B[i]^B[i-1])
    b = b[:] + b[:]

    ah = RollingHash(a)
    bh = RollingHash(b)

    h = ah.calc(0, N)
    ans = []
    for k in range(N):
        if bh.calc(N-k, N-k+N) == h:
            ans.append('%d %d' % (k, A[0]^B[(N-k)%N]))


    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')


if __name__ == '__main__':
    main()