← 返回题目列表

Codeforces · 1218/E

E. 产品元组

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

在石瀑布的神秘区域中漫游时,为了掉落传奇战利品,一名冒险家接到了如下任务。他得到了一个长度为 $$$N$$$ 的数组 $$$A = {a_1,a_2,...,a_N }$$$ 和一个数字 $$$K$$$。

将数组 $$$B$$$ 定义为 $$$B(q, A) = $$$ { $$$q-a_1, q-a_2, ..., q-a_N$$$ }。将函数 $$$F$$$ 定义为 $$$F(B,K)$$$ 是数组 $$$B$$$ 中所有元素 $$$K$$$ 元组的乘积之和。例如,如果数组 $$$B$$$ 为 $$$[2,3,4,5]$$$,并且 $$$K=3$$$,则所有 3 元组的乘积之和为 $$$$$$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$$$$$

然后给他一个数字 Q,即两种类型的查询数量:

- 类型 1:给定 $$$q$$$、$$$i$$$ 和 $$$d$$$ 计算 $$$F(B(q, A), K)$$$,其中我们将初始数组更改为 $$$A[i] = d$$$。
- 类型 2:给定 $$$q$$$、$$$L$$$、$$$R$$$ 和 $$$d$$$ 计算 $$$F(B(q, A), K)$$$,其中我们将初始数组更改为 $$$A[i] = A[i] + d$$$,包括 $$$[L, R]$$$ 范围内的所有 $$$i$$$。

所有更改都是临时对初始数组进行的,并且不会传播到后续查询。帮助冒险家计算任务的答案,并最终获得战利品!

输入

在前两行中,数字 $$$N$$$ ($$$1 \leq N \leq 2*10^4$$$) 和 $$$K$$$ ($$$1 \leq K \leq N$$$)、初始数组 $$$A$$$ 的长度和元组大小,后跟 $$$a_1,a_2,a_3,…,a_N$$$ ($$$0 \leq a_i \leq 10^9$$$) ,数组 $$$A$$$ 的元素,在下一行。然后是数字 $$$Q$$$ ($$$Q \leq 10$$$),即查询数。接下来的 $$$Q$$$ 行中出现以下形式的查询:

- 1 q i d,对于类型 1,
- 2 q L R d,对于类型 2,

如上所述 ($$$0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$$$)

输出

打印 $$$Q$$$ 行,查询的答案,以 $$$998244353$$$ 为模。

示例

输入 #1

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

输出 #1

85
127
63

注意

在第一个查询数组 A = [1, 2, 3, 4, 5],B = [5, 4, 3, 2, 1] 中,2 元组的乘积之和 = 85。

在第二个查询数组中 A = [1, 2, 3, 4, 2],B = [5, 4, 3, 2, 4],2元组的乘积之和 = 127

在第三个查询数组中 A = [1, 3, 4, 4, 5],B = [5, 3, 2, 2, 1],2元组的乘积之和 = 63