K - Kick Away
Earlgray
3
s
1024
MB
100
点
問題文
長さが $2$ 以上の正整数列 $B$ に対し、以下のような問題を考えます。
はじめ、あなたは空集合 $S$ を持っています。あなたは以下の操作を好きな順番で好きな回数行うことができます。
- 操作 $1$ ：$1\leq i \leq |B|$ を満たす $i$ を一つ選ぶ。その後、$B_i$ を $1$ 減らし、$1\leq j \leq |B|,\ i\neq j$ を満たす $j$ を一つ一様ランダムに選び、$B_j$ を $1$ 増やす。
- 操作 $2$ ：$1\leq i \leq |B|,\ B_i=0,\ i \notin S$ を満たす $i$ を一つ選ぶ。その後、$S$ に $i$ を追加する。
$|S|=|B|$ とするために必要な操作 $1$ の回数の期待値が最小となるようにあなたが操作を行うとき、操作 $1$ が行われる回数の期待値 $\bmod 998244353$ を求めてください。
正整数 $K$と長さ $N$ の正整数列 $A_1,A_2,\ldots,A_N$ が与えられます。$i=1,2,\ldots,N-K+1$ について、上の問題で $B=(A_i,A_{i+1},\ldots,A_{i+K-1})$ としたときの答えを求めてください。
期待値 $\bmod 998244353$ の定義
この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 $\frac{y}{x}$ で表したときに $x$ が $998244353$ で割り切れないことが保証されます。 このとき、$y\equiv xz (\bmod 998244353)$ を満たす $0\leq z<998244353$ がただ一つ存在するので、$z$ を出力してください。制約
- $2\leq K \leq N \leq 2\times 10^5$
- $1\leq A_i \leq 10^9$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$N\ K$
$A_1\ A_2\ \ldots\ A_N$
出力
$N-K+1$ 行出力せよ。$i$ 行目には $B=(A_i,A_{i+1}\ldots A_{i+K-1})$ の答えを出力せよ。
入力例 1
3 3
3 2 9
出力例 1
18
$B=(3,2,9)$ のときを考えます。
このとき $i=1$ として操作 $1$ を行うと、$\frac12$ の確率で $B=(2,3,9)$ 、$\frac12$ の確率で $B=(2,2,10)$ となります。また、$0$ である項がないので、操作 $2$ は行えません。また、$B=(2,3,9)$ のときに、$i=1$ として操作 $1$ を $2$ 回行って、もし $B=(0,4,10)$ となれば、$i=1$ として操作 $2$ が行え、$S=\{1\}$ となります。
操作 $1$ を行う回数が最小化されるよう適切に操作すると、そのときの操作 $1$ を行う回数の期待値が $18$ 回となることが示せるので、$18$ を出力します。
入力例 2
5 3
2 8 5 1 4
出力例 2
20
249561106
748683278
入力例 3
2 2
1 1
出力例 3
3