CF1218E.Product Tuples

While roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array $A = {a_1,a_2,...,a_N }$ of length $N$, and a number $K$.

Define array $B$ as $B(q, A) = $ { $q-a_1, q-a_2, ..., q-a_N$ }. Define function $F$ as $F(B,K)$ being sum of products of all $K$-tuples of elements in array $B$. For example, if the array $B$ is $[2,3,4,5]$, and with $K=3$, sum of products of all 3-tuples is $$F(B, 3) = 2*3*4+2*3*5+3*4*5+2*4*5$$

He was then given a number Q, number of queries of two types:

• Type 1: Given $q$, $i$, and $d$ calculate $F(B(q, A), K)$ where we make change to initial array as $A[i] = d$.
• Type 2: Given $q$, $L$, $R$, and $d$ calculate $F(B(q, A), K)$ where we make change to initial array as $A[i] = A[i] + d$ for all $i$ in range $[L, R]$ inclusive.

All changes are temporarily made to initial array, and don't propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!

在石落之地（Stonefalls）的神秘区域游历时，为了获取传奇战利品，一名冒险者接到如下任务：他获得了一个长度为 $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$，则所有三元组乘积之和为

F(B, 3) = 2\*3\*4+2\*3\*5+3\*4\*5+2\*4\*5

随后，他获得一个整数 $Q$，表示有 $Q$ 个查询，查询分为两类：

• 类型 1：给定 $q$、$i$ 和 $d$，计算 $F(B(q, A), K)$，其中对初始数组进行临时修改：令 $A[i] = d$。
• 类型 2：给定 $q$、$L$、$R$ 和 $d$，计算 $F(B(q, A), K)$，其中对初始数组进行临时修改：对所有下标 $i \in [L, R]$（含端点），令 $A[i] = A[i] + d$。

所有修改均为对初始数组的临时修改，不会影响后续查询。请帮助这位冒险者完成任务，最终赢得那份传奇战利品！

In the first two lines, numbers $N$ ($1 \leq N \leq 2*10^4$) and $K$ ($1 \leq K \leq N$), the length of initial array $A$, and tuple size, followed by $a_1,a_2,a_3,…,a_N$ ($0 \leq a_i \leq 10^9$) , elements of array $A$, in the next line. Then follows number $Q$ ($Q \leq 10$), number of queries. In the next $Q$ lines come queries of the form:

• 1 q i d, for type 1,
• 2 q L R d, for type 2,

as explained above ($0 \leq q, d \leq 10^9, 1 \leq i,L,R \leq N$)

前两行分别输入整数 $N$（$1 \leq N \leq 2 \times 10^4$）和 $K$（$1 \leq K \leq N$），表示初始数组 $A$ 的长度以及元组大小；接下来一行输入 $a_1, a_2, a_3, \dots, 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$）。

Print $Q$ lines, the answers to queries, modulo $998244353$.

输出 $Q$ 行，即各查询的答案，对 $998244353$ 取模。

In the first query array A = [1, 2, 3, 4, 5], B = [5, 4, 3, 2, 1], sum of products of 2-tuples = 85.

In second query array A = [1, 2, 3, 4, 2], B = [5, 4, 3, 2, 4], sum of products of 2-tuples = 127

In third query array A = [1, 3, 4, 4, 5], B = [5, 3, 2, 2, 1], sum of products of 2-tuples = 63

第一次查询：数组 A = [1, 2, 3, 4, 5]，B = [5, 4, 3, 2, 1]，所有二元组乘积之和 = 85。

第二次查询：数组 A = [1, 2, 3, 4, 2]，B = [5, 4, 3, 2, 4]，所有二元组乘积之和 = 127。

第三次查询：数组 A = [1, 3, 4, 4, 5]，B = [5, 3, 2, 2, 1]，所有二元组乘积之和 = 63