k707. 老鼠愛前綴和 - 高中生程式解題系統

內容

老鼠在「臺灣首家線上程式解題系統」看到了一題前綴和：

給一個數列 $a_{1} \sim a_{n}$ ，請你求出這個數列的前綴和數列 ${pre}_{1} \sim {pre}_{n}$ ， ${pre}_{i} = \sum_{j = 1}^{i} a_{j} = a_{1} + a_{2} + \dots + a_{i}$ ，也就是數列 $a$ 前 $i$ 項的和。

因為老鼠曾經被軒教授做過生化實驗，所以他非常聰明（但是會塑膠別人），於是他想到這題的加強版：

給 $a_{1} \sim a_{n}$ ， $pre (0, i) = a_{i}$ ， $pre (k, i) = \sum_{j = 1}^{i} pre (k - 1, j) (k \geq 1)$ ， $pre (k, i)$ 其實就是對陣列 $a$ 做 $k$ 次前綴和的第 $i$ 項！

現在老鼠告訴你 $n, k, a_{1} \sim a_{n}$ 是多少，請你求出 $pre (k, 1) \sim pre (k, n) (mod 998244353)$ 。

Caido 解不出這題，於是他寄信給老鼠：「我的臺灣首家線上程式解題系統 id 是 089487122，你現在把 Code 給我，我承諾讓你的名字出現在我的題目上，謝謝，pls！」

輸入說明

第一行有兩個正整數 $n, k$ ，代表數列長度與做幾次前綴和。

第二行有 $n$ 個整數 $a_{1} \sim a_{n}$ 。

$1 \leq n \leq 10^{5}$
$1 \leq k < 998244353$
$0 \leq a_{i} < 998244353$

輸出說明

輸出一行 $n$ 個整數，代表 $pre (k, 1) \sim pre (k, n) (mod 998244353)$ 。

範例輸入 #1

5 3
1 1 1 1 1

範例輸出 #1

1 4 10 20 35

範例輸入 #2

10 491867288
763006201 667152635 817997967 777669966 640753723 933924751 37374949 723562787 360466089 171347400

範例輸出 #2

763006201 734128003 192600514 512702337 117875800 107877905 556952120 829596794 325383858 411656639

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (20%): 2.0s , <1K
公開測資點#1 (20%): 2.0s , <1M
公開測資點#2 (20%): 2.0s , <1M
公開測資點#3 (20%): 2.0s , <1M
公開測資點#4 (20%): 2.0s , <1M

提示：

$100 % ：無特別限制$

標籤:

數學

出處:

[管理者：

becaido (Caido) ]

編號	身分	題目	主題	人氣	發表日期
36605	1164007-3@g. ... (oier_without_op)	k707	AC，但不光彩	407	2023-07-27 00:59