No.2754 Cumulate and Drop
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : 👑
箱星
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 45
作問者 : 👑
箱星
/ テスター :
👑 p-adic
問題文最終更新日: 2024-05-15 10:36:04
問題文
数列 $(a_1,a_2,\ldots,a_n)$ に対して、$b_i=a_1+\cdots+a_i$ により定まる数列 $(b_1,b_2,\ldots,b_n)$ を累積和と呼ぶことにします。
長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。数列の長さが $1$ になるまで、以下の操作を繰り返します。
- 数列 $A$ を累積和で置き換える。その後、数列 $A$ の先頭の項を捨てる。
数列の長さが $1$ になったとき、その項を $998244353$ で割った余りを求めてください。
制約
- $1\le N\le 2\times 10^5$
- $0\le A_i< 998244353$
- 入力はすべて整数
入力
$N$ $A_1$ $A_2$ $\cdots$ $A_N$
出力
最後に改行してください。
サンプル
サンプル1
入力
3 1 0 2
出力
4
はじめ数列は $(1,0,2)$ です。累積和をとり先頭の項を捨てると $(1,3)$ となります。再び累積和をとり先頭の項を捨てると $(4)$ となります。$4$ を出力します。
サンプル2
入力
9 3 1 4 1 5 9 2 6 5
出力
12784
サンプル3
入力
2 900000000 800000000
出力
701755647
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。