YZOJ P4611 区间加多项式(YJC 的数组/多项式?)
时间限制:4444MS 内存限制:1048576KB
难度:7.2
-
题目描述
由于本题之前被*了,所以现在数据就是随便造的,可能会因为太水又被艹 //给出题人留点面子吧qwq
YJC 在 AK 了一场校内之后,对其中的一题(P2036 「A Simple Data Structure Problem II 」)产生了兴趣。
于是他出了一题加强版(P4316 「ASDSP VII —— YJC树」),然而,他还是觉得这个加强版太简单啦!!!
所以,这次,他不仅把 K \leq 5 往后面加了三个零变成了 K \leq 5000 ,还对询问做了一点修改!
喜欢差分的 YJC 有一个长度为 N 的数组 c,初始值都为 0,下标编号为 1, 2, \cdots, N 。
现在 YJC 忙着 AK CSP-S2019,没空验证数据的正确性,所以只能把这个重任交给了你 —— ******,希望你能写一个程序帮他实现以下的几个操作:
opt=1,给定 L, R,输出 \sum\limits_{i=L}^R c_i 的值对 998244353 取模后的结果;
opt=0,给定 L, R 以及 K 次多项式 f(x)=\sum\limits_{k=0}^K a_kx^k,对 c_L, c_{L+1}, \cdots, c_R 分别加上 f(1), f(2), \cdots, f(R-L+1) 的值。
-
输入格式
第一行两个正整数 N, Q ,分别表示区间范围 [1, N] 及询问数 Q 。
接下来,每行(除了每个 opt=0 操作的下一行)的第一个数 opt 表示操作类型。
若 opt=0,则接下来有两个正整数 L, R 表示操作的区间 [L, R]。紧接着下一行的第一个整数 K 表示多项式的最高次数为 K ,接下来 K+1 个整数 a_0, a_1, \cdots, a_K 分别表示多项式 f(x)= \displaystyle\sum\limits_{k=0}^K a_kx^k 的系数;
若 opt=1,则接下来有两个正整数 L, R 表示询问的区间 [L, R]。
因为 YJC 忙着 AK CSP-S2019(之前说过了),所以他一不小心把数据给加密了。