k707. 老鼠愛前綴和
Tags : 數學
Accepted rate : 4人/8人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-06-07 06:47

Content

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

給一個數列 $a_1\sim a_n$,請你求出這個數列的前綴和數列 $\text{pre}_1\sim \text{pre}_n$,$\text{pre}_i=\sum\limits_{j=1}^ia_j=a_1+a_2+\dots +a_i$,也就是數列 $a$ 前 $i$ 項的和。

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

給 $a_1\sim a_n$,$\text{pre}(0,i)=a_i$,$\text{pre}(k,i)=\sum\limits_{j=1}^i\text{pre}(k-1,j)\ (k\geq 1)$,$\text{pre}(k,i)$ 其實就是對陣列 $a$ 做 $k$ 次前綴和的第 $i$ 項!

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

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

Input

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

第二行有 $n$ 個整數 $a_1\sim a_n$。

  • $1\leq n\leq 10^5$
  • $1\leq k<998244353$
  • $0\leq a_i<998244353$
Output

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

Sample Input #1
5 3
1 1 1 1 1
Sample Output #1
1 4 10 20 35
Sample Input #2
10 491867288
763006201 667152635 817997967 777669966 640753723 933924751 37374949 723562787 360466089 171347400
Sample Output #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
Hint :

$100\%:無特別限制$

Tags:
數學
出處:
[管理者: becaido (Caido) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
36605 1164007-3@g. ... (oier_without_op) k707
AC,但不光彩
298 2023-07-27 00:59