luogu#P5641. 【CSGRound2】开拓者的卓识

    ID: 9663 远端评测题 200ms 125MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>数论数学快速傅里叶变换,FFT快速数论变换 NTT洛谷月赛

【CSGRound2】开拓者的卓识

题目背景

(上图转载于某神仙的题目描述)

小 K 又在做白日梦了。他进入到他的幻想中,发现了一个非常有趣的序列aa和一个非常有趣的数kk

题目描述

我们记一个序列 [l,r][l,r]kk 阶子段和为 sumk,l,rsum_{k,l,r},有

$$sum_{k,l,r}=\begin{cases}\sum\limits_{i=l}^{r}a_i&,k=1\\\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}sum_{k-1,i,j}&,k\geq 2\end{cases} $$

他现在站在位置 11 上,他每一次往右开拓一个格子就可以增加他 IOI 赛场的 rp,所以他想尽可能的多开拓格子。可是每一次他从 rr 开拓到 r+1r+1 需要正确的回答 sumk,1,rsum_{k,1,r}。小 K 不屑于算,就把任务交给你了。

输入格式

两行。第一行 n,kn,k,表示 aa 的长度和 kk

第二行 nn 个正整数,表示 aa

输出格式

一行,第 ii 个数为 sumk,1,isum_{k,1,i}。由于答案过大,您只需要求出答案对 998244353998244353 取模的值。

3 1
1 2 3
1 3 6
3 2
1 2 3
1 6 20
3 10
1 2 3
1 30 420

提示

样例解释 2

sum2,1,1=sum1,1,1=1sum_{2,1,1}=sum_{1,1,1}=1

$sum_{2,1,2}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,2,2}=1+3+2=6$

$sum_{2,1,3}=sum_{1,1,1}+sum_{1,1,2}+sum_{1,1,3}+sum_{1,2,2}+sum_{1,2,3}+sum_{1,3,3}=1+3+6+2+5+3=20$

数据范围

测试点编号 nn 的范围 kk 的范围 aia_i 的范围
121\sim 2 10\le 10
383\sim 8 103\le 10^3 105\le 10^5
99 105\le 10^5 =1=1 998244353\le 998244353
1010 =2=2
1111 =3=3
1212 10\le 10
131713\sim 17 102\le 10^2
1818 105\le 10^5
192519\sim 25 998244353\le 998244353