B - Nbonacci Sequence

2 secs 1024 MB
loop0919's icon loop0919

問題

長さ NN の整数列 AA が与えられます。
正整数 xx に関する関数 f(x)f(x) を次のように定義します。

  • f(x)={Ax( if1xN )f(x1)+f(x2)++f(xN)( ifxN+1 )\displaystyle f(x) = \begin{cases} A_x \enspace ( \ \mathrm{if} \enspace 1 \leq x \leq N \ ) \\ f(x-1) + f(x-2) + \ldots + f(x-N) \enspace ( \ \mathrm{if} \enspace x \geq N+1 \ ) \end{cases}

f(X)f(X)998244353998244353 で割った余りを求めてください。

制約

  • 1N2×1051 \leq N \leq 2 \times 10^5
  • 1X5×1051 \leq X \leq 5 \times 10^5
  • 0Ai998244352(1iN)0 \leq A_i \leq 998244352 \enspace (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NNXX
A1  ANA_1 \ \dots \ A_N

出力

答えを出力せよ。

サンプル 1

入力1
2 5
1 1
出力1
5

このような計算をすれば答えを求めることができます。

  • f(1)=A1=1f(1) = A_1 = 1
  • f(2)=A2=1f(2) = A_2 = 1
  • f(3)=f(2)+f(1)=2f(3) = f(2) + f(1) = 2
  • f(4)=f(3)+f(2)=3f(4) = f(3) + f(2) = 3
  • f(5)=f(4)+f(3)=5f(5) = f(4) + f(3) = 5

よって、答えは 55 となります。

サンプル 2

入力2
15 10000
806413653 500940409 485353637 91489265 310431898 771043380 712137305 711436923 575371013 800850108 251980687 446868718 772636473 949053376 619975694
出力2
846683190

998244353998244353 で割った余りを求めてください。

Submit


Go (1.21)