Sum of Paths (Codeforces 1467D)
Tags: Math, combinatorics

There are $$$n$$$ cells, numbered $$$1,2,\dots, n$$$ from left to right. You have to place a robot at any cell initially. The robot must make exactly $$$k$$$ moves.In one move, the robot must move one cell to the left or right, provided that it doesn't move out of bounds. In other words, if the robot was in the cell $$$i$$$, it must move to either the cell $$$i-1$$$ or the cell $$$i+1$$$, as long as it lies between $$$1$$$ and $$$n$$$ (endpoints inclusive). The cells, in the order they are visited (including the cell the robot is placed), together make a good path.Each cell $$$i$$$ has a value $$$a_i$$$ associated with it. Let $$$c_0, c_1, \dots, c_k$$$ be the sequence of cells in a good path in the order they are visited ($$$c_0$$$ is the cell robot is initially placed, $$$c_1$$$ is the cell where the robot is after its first move, and so on; more formally, $$$c_i$$$ is the cell that the robot is at after $$$i$$$ moves). Then the value of the path is calculated as $$$a_{c_0} + a_{c_1} + \dots + a_{c_k}$$$.Your task is to calculate the sum of values over all possible good paths. Since this number can be very large, output it modulo $$$10^9 + 7$$$. Two good paths are considered different if the starting cell differs or there exists an integer $$$i \in [1, k]$$$ such that the current cell of the robot after exactly $$$i$$$ moves is different in those paths.You must process $$$q$$$ updates to $$$a$$$ and print the updated sum each time. Each update changes the value of exactly one cell. See the input format and the sample input-output for more details.

Input: The first line of the input contains three space-separated integers $$$n$$$, $$$k$$$ and $$$q$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k \le 5000$$$; $$$1 \le q \le 2 \cdot 10^5$$$).The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).$$$q$$$ lines follow. Each line contains two space-separated integers $$$i$$$ and $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 10^9$$$) indicating that you must change the value of $$$a_i$$$ to $$$x$$$.

Output: Print $$$q$$$ integers. The $$$i$$$-th integer should be the sum of values over all good paths after the first $$$i$$$ updates are performed. Since the answers may be large, print them modulo $$$10^9 + 7$$$.

Note: In the first example, the good paths are $$$(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)$$$.Initially the values of $$$a$$$ are $$$[3, 5, 1, 4, 2]$$$. After the first update, they become $$$[9, 5, 1, 4, 2]$$$. After the second update, they become $$$[9, 4, 1, 4, 2]$$$, and so on.

Sample Inputs:
5 1 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2

5 2 5
3 5 1 4 2
1 9
2 4
3 6
4 6
5 2

4 40 6
92 21 82 46
3 56
1 72
4 28
1 97
2 49
2 88

Sample Outputs:
62
58
78
86
86

157
147
207
227
227

239185261
666314041
50729936
516818968
766409450
756910476

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

    def __init__(self, file):
        self.newlines = 0
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def S():
    return input().strip()

def print_list(l):
    print(' '.join(map(str, l)))
M = 10 ** 9 + 7
(n, k, q) = RL()
a = [0] + RLL() + [0]
count = [[0] * (n // 2 + 2) for _ in range(k + 1)]
count[0][1:-1] = [1] * n
(ii, jj) = ((n - 1) // 2 + 1, n // 2)
for t in range(1, k + 1):
    for i in range(1, (n - 1) // 2 + 1):
        count[t][i] = (count[t - 1][i - 1] + count[t - 1][i + 1]) % M
    count[t][ii] = (count[t - 1][ii - 1] + count[t - 1][jj]) % M
res = [0] * (n + 2)
for i in range(1, (n + 1) // 2 + 1):
    for j in range((k + 1) // 2):
        res[i] = (res[i] + count[j][i] * count[k - j][i]) % M
    res[i] = res[i] * 2 % M
    if k & 1 == 0:
        res[i] = (res[i] + count[k // 2][i] ** 2) % M
for i in range((n + 1) // 2 + 1, n + 1):
    res[i] = res[n + 1 - i]
s = 0
for i in range(1, n + 1):
    s = (s + a[i] * res[i]) % M
for _ in range(q):
    (i, x) = RL()
    s = (s + (x - a[i]) * res[i]) % M
    a[i] = x
    print(s)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

    def __init__(self, file):
        self.newlines = 0
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def S():
    return input().strip()

def print_list(l):
    print(' '.join(map(str, l)))
M = 10 ** 9 + 7
(n, k, q) = RL()
a = [0] + RLL() + [0]
count = [[0] * (n + 2) for _ in range(k + 1)]
count[0][1:-1] = [1] * n
for t in range(1, k + 1):
    for i in range(1, n + 1):
        count[t][i] = (count[t - 1][i - 1] + count[t - 1][i + 1]) % M
res = [0] * (n + 2)
for i in range(1, (n + 1) // 2 + 1):
    for j in range((k + 1) // 2):
        res[i] = (res[i] + count[j][i] * count[k - j][i]) % M
    res[i] = res[i] * 2 % M
    if k & 1 == 0:
        res[i] = (res[i] + count[k // 2][i] * count[k // 2][i]) % M
for i in range((n + 1) // 2 + 1, n + 1):
    res[i] = res[n + 1 - i]
s = 0
for i in range(1, n + 1):
    s = (s + a[i] * res[i]) % M
for _ in range(q):
    (i, x) = RL()
    s = (s + (x - a[i]) * res[i]) % M
    a[i] = x
    print(s)

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):

    def __init__(self, file):
        self.newlines = 0
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
    return map(int, sys.stdin.readline().split())

def RLL():
    return list(map(int, sys.stdin.readline().split()))

def N():
    return int(input())

def S():
    return input().strip()

def print_list(l):
    print(' '.join(map(str, l)))
M = 10 ** 9 + 7
(n, k, q) = RL()
a = [0] + RLL() + [0]
count = [[0] * (n + 2) for _ in range(k + 1)]
count[0][1:-1] = [1] * n
for t in range(1, k + 1):
    for i in range(1, n + 1):
        count[t][i] = (count[t - 1][i - 1] + count[t - 1][i + 1]) % M
res = [0] * (n + 2)
for i in range(1, (n + 1) // 2 + 1):
    for j in range((k + 1) // 2):
        res[i] = (res[i] + count[j][i] * count[k - j][i] % M) % M
    res[i] = res[i] * 2 % M
    if k & 1 == 0:
        res[i] = (res[i] + count[k // 2][i] * count[k // 2][i] % M) % M
for i in range((n + 1) // 2 + 1, n + 1):
    res[i] = res[n + 1 - i]
s = 0
for i in range(1, n + 1):
    s = (s + a[i] * res[i] % M) % M
for _ in range(q):
    (i, x) = RL()
    s = (s + (x - a[i]) * res[i] % M) % M
    a[i] = x
    print(s)