题目描述

問題 F と問題 F2 は同じ問題ですが、制約と実行時間制限が異なります。

高橋君の倉庫には $N$ 本のワインがあり、左右方向 $1$ 列に並んでいます。左から $i$ 番目のワインの美味しさは $A_i$ です。
青木君は今からこの $N$ 本のうち、ちょうど $K$ 本を選んで盗みます。しかし、高橋君は注意深いので、以下の条件が満たされると盗まれたことに気付いてしまいます。

• 連続で並ぶ $D$ 本のワインであって、そのうち $2$ 本以上盗まれているようなものが存在する

高橋君に気付かれないような全ての盗み方について、盗んだワインの美味しさの和を求め、それを足し合わせた値を求めてください。
なお、答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

输入格式

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

$N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

答えを $998244353$ で割った余りを出力せよ。

题目大意

给定含有 $n$ 个元素的序列 $\{A\}$，现在要求选出含有 $k$ 个元素的子序列，满足不能存在在原序列 $\{A\}$ 中距离差小于等于$D$的元素（即 $A_i$ 选了 $\forall i-D+1 \leq j \leq i+D-1$ $A_{j}$ 就不能选了）。问所有可能的子序列的权值和。

4 2 2
1 4 2 3

14

5 2 3
1 5 7 7 3

20

18 4 4
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467

228955567

提示

制約

• $2\ \le\ D\ \le\ N\ \le\ 10^6$
• $ 1\ \le\ K\ \le\ \left\lceil\ \frac{N}{D}\ \right\rceil $ （$\left\lceil\ x\ \right\rceil$ は $x$ 以上の最小の整数を表す）
• $1\ \le\ A_i\ \lt\ 998244353$
• 入力に含まれる値は全て整数

Sample Explanation 1

盗み方と盗んだワインの美味しさの和は以下の通りです。 - 左から $1$ 本目のワインと $3$ 本目のワインを盗んだ場合 : 美味しさの和は $1\ +\ 2\ =\ 3$ - 左から $1$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $1\ +\ 3\ =\ 4$ - 左から $2$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $4\ +\ 3\ =\ 7$ よって答えは $3\ +\ 4\ +\ 7\ =\ 14$ となります。

Sample Explanation 2

盗み方と盗んだワインの美味しさの和は以下の通りです。 - 左から $1$ 本目のワインと $4$ 本目のワインを盗んだ場合 : 美味しさの和は $1\ +\ 7\ =\ 8$ - 左から $1$ 本目のワインと $5$ 本目のワインを盗んだ場合 : 美味しさの和は $1\ +\ 3\ =\ 4$ - 左から $2$ 本目のワインと $5$ 本目のワインを盗んだ場合 : 美味しさの和は $5\ +\ 3\ =\ 8$