Product Tuples

题意翻译

给定一个序列 $A=a_1,a_2,\cdots,a_n$ 以及一个数 $K$。 对于给定值 $q$，定义序列 $B(q,A)=b_1,b_2,\cdots,b_n$，$b_i=q-a_i$。 定义 $F(B,K)$ 表示从序列 $B$ 中选择 $K$ 个数相乘，所有选择方法的积的和。 $Q$ 次 **独立操作**（即每次操作不会影响到后续），有如下两种方式： - 给定 $q,i,d$，询问将 $a_i$ 修改为 $d$ 后 $F(B(q,A),K)$ 的值。 - 给定 $q,L,R,d$，询问将 $a_{L\dots R}$ 增加 $d$ 后 $F(B(q,A),K)$ 的值。 $1\leq n\leq 2\times 10^4,1\leq K\leq n,0\leq a_i\leq 10^9,Q\leq 10$，每次操作 $0\leq q,d\leq 10^9,1\leq i,L,R\leq n$。

题目描述

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 $ $ </p><p>He was then given a number Q, number of queries of two types: </p><ul> <li> Type 1: Given $ q $ , $ i $ , and $ d $ calculate $ F(B(q, A), K) $ where we make change to initial array as $ A\[i\] = d $ . </li><li> 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!

输入输出格式

输入格式

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 $ )

输出格式

Print $ Q $ lines, the answers to queries, modulo $ 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

说明

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