← 返回题目列表

Codeforces · 1467/D

D. 路径总和

中文机器翻译题面 查看原题

有 $$$n$$$ 个单元格,从左到右编号为 $$$1,2,\dots, n$$$。您最初必须将机器人放置在任何单元格中。机器人必须精确地进行 $$$k$$$ 移动。

在一次移动中,机器人必须向左或向右移动一个单元格,前提是它不移出边界。换句话说,如果机器人位于单元格 $$$i$$$ 中,则它必须移动到单元格 $$$i-1$$$ 或单元格 $$$i+1$$$,只要它位于 $$$1$$$ 和 $$$n$$$ 之间(包括端点)。这些单元按照访问的顺序(包括机器人放置的单元)一起形成一条良好的路径。

每个单元格 $$$i$$$ 都有一个与其关联的值 $$$a_i$$$。令 $$$c_0, c_1, \dots, c_k$$$ 为良好路径中的单元序列,按照它们被访问的顺序排列($$$c_0$$$ 是单元机器人最初放置的单元,$$$c_1$$$ 是机器人在第一次移动后所在的单元,依此类推;更正式地说,$$$c_i$$$ 是机器人在 $$$i$$$ 移动后所在的单元)。然后路径的值计算为 $$$a_{c_0} + a_{c_1} + \dots + a_{c_k}$$$。

您的任务是计算所有可能的良好路径的值总和。由于这个数字可能非常大,因此输出它对 $$$10^9 + 7$$$ 取模。如果起始单元不同或 [1, k]$$$ 中存在整数 $$$i \in 使得机器人在 $$$i$$$ 移动后的当前单元在这些路径中不同,则认为两条好路径不同。

您必须处理 $$$q$$$ 对 $$$a$$$ 的更新,并每次打印更新后的总和。每次更新都会更改一个单元格的值。有关更多详细信息,请参阅输入格式和示例输入输出。

输入

输入的第一行包含三个空格分隔的整数 $$$n$$$、$$$k$$$ 和 $$$q$$$ ($$$2 \le n \le 5000$$$; $$$1 \le k \le 5000$$$; $$$1 \le q \le 2 \cdot 10^5$$$)。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。 接下来是

$$$q$$$ 行。每行包含两个空格分隔的整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 10^9$$$),表示必须将 $$$a_i$$$ 的值更改为 $$$x$$$。

输出

打印 $$$q$$$ 整数。第 $$$i$$$ 个整数应该是执行第一个 $$$i$$$ 更新后所有良好路径上的值之和。由于答案可能很大,请以 $$$10^9 + 7$$$ 为模打印它们。

示例

输入 #1

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

输出 #1

62
58
78
86
86

输入 #2

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

输出 #2

157
147
207
227
227

输入 #3

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

输出 #3

239185261
666314041
50729936
516818968
766409450
756910476

注意

在第一个示例中,好的路径是 $$$(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)$$$。

最初 $$$a$$$ 的值为 $$$[3, 5, 1, 4, 2]$$$。第一次更新后,它们变成 $$$[9, 5, 1, 4, 2]$$$。第二次更新后,它们变成$$$[9,4,1,4,2]$$$,依此类推。