Fibonacci Additions (Codeforces 1634F)
Tags: Math, hashing

One of my most productive days was throwing away 1,000 lines of code.— Ken ThompsonFibonacci addition is an operation on an array $$$X$$$ of integers, parametrized by indices $$$l$$$ and $$$r$$$. Fibonacci addition increases $$$X_l$$$ by $$$F_1$$$, increases $$$X_{l + 1}$$$ by $$$F_2$$$, and so on up to $$$X_r$$$ which is increased by $$$F_{r - l + 1}$$$.$$$F_i$$$ denotes the $$$i$$$-th Fibonacci number ($$$F_1 = 1$$$, $$$F_2 = 1$$$, $$$F_{i} = F_{i - 1} + F_{i - 2}$$$ for $$$i > 2$$$), and all operations are performed modulo $$$MOD$$$.You are given two arrays $$$A$$$ and $$$B$$$ of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays $$$A$$$ and $$$B$$$ are equal modulo $$$MOD$$$.

Input: The first line contains 3 numbers $$$n$$$, $$$q$$$ and $$$MOD$$$ ($$$1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$$$) — the length of the arrays, the number of operations, and the number modulo which all operations are performed.The second line contains $$$n$$$ numbers — array $$$A$$$ ($$$0 \le A_i < MOD$$$).The third line also contains $$$n$$$ numbers — array $$$B$$$ ($$$0 \le B_i < MOD$$$).The next $$$q$$$ lines contain character $$$c$$$ and two numbers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) — operation parameters. If $$$c$$$ is "A", Fibonacci addition is to be performed on array $$$A$$$, and if it is is "B", the operation is to be performed on $$$B$$$.

Output: After each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.

Note: Explanation of the test from the condition: Initially $$$A=[2,2,1]$$$, $$$B=[0,0,0]$$$. After operation "A 1 3": $$$A=[0,0,0]$$$, $$$B=[0,0,0]$$$ (addition is modulo 3). After operation "A 1 3": $$$A=[1,1,2]$$$, $$$B=[0,0,0]$$$. After operation "B 1 1": $$$A=[1,1,2]$$$, $$$B=[1,0,0]$$$. After operation "B 2 2": $$$A=[1,1,2]$$$, $$$B=[1,1,0]$$$. After operation "A 3 3": $$$A=[1,1,0]$$$, $$$B=[1,1,0]$$$.

Sample Inputs:
3 5 3
2 2 1
0 0 0
A 1 3
A 1 3
B 1 1
B 2 2
A 3 3

5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2

Sample Outputs:
YES
NO
NO
NO
YES

NO
NO
YES

Solution (Python):
import io, os
read = io.BytesIO(os.read(0, os.fstat(0).st_size))
I = lambda : read.readline().split()
(n, q, M) = map(int, I())
F = [1, 1]
period = None
for i in range(n - 1):
    F.append((F[-1] + F[-2]) % M)
A = [*map(int, I())]
B = [*map(int, I())]
d = [(A[i] - B[i]) % M for i in range(n)]
fd = [d[0]]
if n > 1:
    fd.append((d[1] - d[0]) % M)
for i in range(2, n):
    fd.append((d[i] - d[i - 1] - d[i - 2]) % M)
s = sum(fd)
out = []
for i in range(q):
    (ss, l, r) = I()
    if ss.decode('utf-8') == 'A':
        mul = 1
    else:
        mul = -1
    l = int(l) - 1
    r = int(r)
    s -= fd[l]
    fd[l] = (fd[l] + mul) % M
    s += fd[l]
    if r + 1 < n:
        s -= fd[r + 1]
        fd[r + 1] = (fd[r + 1] - mul * F[r - l - 1]) % M
        s += fd[r + 1]
    if r < n:
        s -= fd[r]
        fd[r] = (fd[r] - mul * F[r - l]) % M
        s += fd[r]
    if s == 0:
        out.append('YES')
    else:
        out.append('NO')
print('\n'.join(out))

Solution (Python):
import io
import os
if __name__ == '__main__':
    read = io.BytesIO(os.read(0, os.fstat(0).st_size))
    I = lambda : read.readline().split()
    (n, q, M) = map(int, I())
    F = [1, 1]
    period = None
    for i in range(n - 1):
        F.append((F[-1] + F[-2]) % M)
    A = [*map(int, I())]
    B = [*map(int, I())]
    d = [(A[i] - B[i]) % M for i in range(n)]
    fd = [d[0]]
    if n > 1:
        fd.append((d[1] - d[0]) % M)
    for i in range(2, n):
        fd.append((d[i] - d[i - 1] - d[i - 2]) % M)
    s = sum(fd)
    out = []
    for i in range(q):
        (ss, l, r) = I()
        if ss.decode('utf-8') == 'A':
            mul = 1
        else:
            mul = -1
        l = int(l) - 1
        r = int(r)
        s -= fd[l]
        fd[l] = (fd[l] + mul) % M
        s += fd[l]
        if r + 1 < n:
            s -= fd[r + 1]
            fd[r + 1] = (fd[r + 1] - mul * F[r - l - 1]) % M
            s += fd[r + 1]
        if r < n:
            s -= fd[r]
            fd[r] = (fd[r] - mul * F[r - l]) % M
            s += fd[r]
        if s == 0:
            out.append('YES')
        else:
            out.append('NO')
    print('\n'.join(out))

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def main():
    (N, Q, MOD) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    FIB = [1, 1]
    for _ in range(N - 1):
        FIB.append((FIB[-1] + FIB[-2]) % MOD)
    C = [(a - b) % MOD for (a, b) in zip(A, B)]
    D = [C[0]]
    if N > 1:
        D.append((C[1] - C[0]) % MOD)
    for i in range(2, N):
        D.append((C[i] - C[i - 1] - C[i - 2]) % MOD)
    S = sum(D)
    out = []
    for _ in range(Q):
        (c, l, r) = input().decode().strip().split()
        (l, r) = (int(l) - 1, int(r) - 1)
        sign = 1 if c == 'A' else -1
        S -= D[l]
        D[l] = (D[l] + sign) % MOD
        S += D[l]
        if r + 1 < N:
            S -= D[r + 1]
            D[r + 1] = (D[r + 1] - sign * FIB[r - l + 1]) % MOD
            S += D[r + 1]
        if r + 2 < N:
            S -= D[r + 2]
            D[r + 2] = (D[r + 2] - sign * FIB[r - l]) % MOD
            S += D[r + 2]
        out.append('YES' if S == 0 else 'NO')
    print('\n'.join(out))
if __name__ == '__main__':
    main()