2634. [HZOI 2016] 数列操作λ

【题目描述】

给出一个长度为$N$的数组和$Q$次操作和一个数$K$

操作分两种

    1.给出$p,x$将位置$p$加上一个值$x$

    2.给出$n$询问到位置$n$的$K$次前缀和$\mod 998244353$

至于什么是K次前缀和,你可以这么理解:

    对于一个数组$a$,对于所有$i$从$1$到$N-1$按顺序令$a_i=a_i+a_{i-1}$可以得到$1$次前缀和,再次执行该操作可以得到$2$次前缀和,即$K$次前缀和就是执行$K$次操作后的结果。例如对于$\{1,1,1,1,1\}$的$1$次前缀和就是$\{1,2,3,4,5\}$,$2$次前缀和就是$\{1,3,6,10,15\}$

$N\le10^5,Q\le 10^5,K\le 2^{30}$

$操作1不超过500次$

【输入格式】

第一行三个整数$N,K,Q$

第二行$N$个数,第$i$个数为数组中位置为$i-1$的数

接下来$Q$行每行行首一个数$op$表示操作种类

    若$op=1$则接下来有两个整数$p,x$

    若$op=2$接下来一个整数$n$

【输出格式】

对于每个$op=2$的操作,输出对应的值

【样例输入】

5 1 2
1 1 1 1 1
1 1 1
2 3

【样例输出】

5

【提示】

对于第$p$个测试点有

$Q,N\le p^2*1000$

$K\le p^2*10737418$

【来源】

51nod 1172 +强行嵌套