比赛场次 358
比赛名称 数列操作练习题
比赛状态 已结束比赛成绩
开始时间 2017-03-18 19:00:00
结束时间 2017-03-19 23:59:59
开放分组 全部用户
注释介绍 数列操作按顺序做=ω=
祝愿大家颓得好成绩
题目名称 数列操作λ
输入输出 meatv.in/out
时间限制 3000 ms (3 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分

数列操作λ

★★★☆   输入文件:meatv.in   输出文件:meatv.out   简单对比
时间限制:3 s   内存限制:512 MiB

【题目描述】

给出一个长度为$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 +强行嵌套