CF1218E Product Tuples

在 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$，那么所有 3 元组乘积之和为 $$ F(B, 3) = 2 \times 3 \times 4 + 2 \times 3 \times 5 + 3 \times 4 \times 5 + 2 \times 4 \times 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)$，其中对初始数组做出更改 $A[i] = A[i] + d$，对于所有 $i$ 在区间 $[L, R]$ 内（包含两端）。 所有更改仅在本次查询中临时生效，不会影响后续查询。请帮助冒险者计算每个查询的答案，助他完成任务，最终获得战利品！

第一行输入两个整数 $N$（$1 \leq N \leq 2 \times 10^4$）和 $K$（$1 \leq K \leq N$），表示初始数组 $A$ 的长度和元组大小。 第二行输入 $a_1, a_2, ..., a_N$（$0 \leq a_i \leq 10^9$），表示数组 $A$ 的元素。 第三行输入一个整数 $Q$（$Q \leq 10$），表示查询的数量。 接下来的 $Q$ 行，每行表示一个查询，格式如下： - 类型 1：`1 q i d` - 类型 2：`2 q L R d` 其中 $0 \leq q, d \leq 10^9$，$1 \leq i, L, R \leq N$。

输出 $Q$ 行，每行一个整数，表示每个查询的答案，对 $998244353$ 取模。

在第一个查询中，数组 $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$。 由 ChatGPT 4.1 翻译