Problem: 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.)

Submission attempts (in order):
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)
    a0 = a1[0]
    for i in memo:
        x = a0 ^ b1[i]
        print(i, x)


main()

def main():
    class rolling_hash():
        def __init__(self, sequence):
            self.sequence = sequence  
            self.seq_size = len(self.sequence)  の長さ
            self.mod = 2**61-1  # mod
            self.base = 3  
            self.Hash_0start = [0]*(self.seq_size+1)  
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    (self.sequence[i]+1)*pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % 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()

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()

Verdicts: Wrong Answer

Time Limit Exceeded

Accepted