No.2661 Sweep Cards (Hard)
タグ : / 解いたユーザー数 6
作問者 :
hamamu
/ テスター :
chineristAC
てんぷら
注意
本問題はEasy版があります。Easy版と異なるのは赤文字の部分のみです。
問題文
$1$ から $N$ の番号がついた $N$ 枚のカードがあります。
番号 $i$ が書かれたカードをカード $i$ と呼びます。
はじめ、カードの山が $N$ 個左右一列に並んでおり、
左から $i$ 番目の山はカード $i$ のみからなっています。
あなたはこの山の列に対して、以下の操作を $0$ 回以上何度でも行えます。
- 山の列の連続部分列で長さ $K$ のものを選ぶ（$K$ は入力で与えられる）
- 選んだ山を左から右の順に左が上になるよう重ねる、または右から左の順に右が上になるよう重ねる
操作の形式的な説明（クリックすると詳細を表示します）
各山を、カード番号を山の上から順に並べた数列 $(a_1,a_2,\cdots,a_n)$ で表します。
山の列を、数列からなる列 $A=(A_1,A_2,\cdots,A_m)$ で表します。
数列 $X=(x_1,x_2,\cdots,x_{m'}),Y=(y_1,y_2,\cdots,y_{m''})$ に対し、
$X+Y$ で $(x_1,x_2,\cdots,x_{m'},y_1,y_2,\cdots,y_{m''})$ を表します。
このとき、操作は以下のとおり表されます：
- $R-L+1=K$ を満たす $2$ つの整数 $L,R\ (1 \leq L < R \leq m)$ を選ぶ
- $A$ を $(A_1,A_2,\dots,A_{L-1},A_L+A_{L+1}+\dots+A_R,A_{R+1},\dots,A_m)$ または $(A_1,A_2,\dots,A_{L-1},A_R+A_{R-1}+\dots+A_L,A_{R+1},\dots,A_m)$ で置き換える
操作の具体例による説明（クリックすると詳細を表示します）
山が $4$ つあり、各山のカード番号が以下のとおりだったとします。
- 左から $1$ 番目の山：上から順に $3,2,1$
- 左から $2$ 番目の山：$4$ のみ
- 左から $3$ 番目の山：上から順に $5,6,7$
- 左から $4$ 番目の山：$8$ のみ
これを(3,2,1),(4),(5,6,7),(8)と表すとします。
これに対する操作例は以下のとおりです。
- 操作例1：$K=2$ で、
(3,2,1),(4)を選び、左から右の順に重ねると、(3,2,1,4),(5,6,7),(8)になります。 - 操作例2：$K=3$ で、
(4),(5,6,7),(8)を選び、右から左の順に重ねると、(3,2,1),(8,5,6,7,4)になります。
$k=1,2,\cdots ,M$ について、山の個数が $X_k$ になるまで操作した後得られるカード配置の個数を $998244353$ で割った余りを求めてください。
ここで、ある2つのカード配置が異なるとは、
「左から $i$ 番目の山の上から $j$ 番目のカードが、両者で異なる、または一方に存在しもう一方に存在しない」
を満たす $(i,j)$ が存在することを意味します。
制約
- 入力は全て整数
- $2 \le N \le$ $10^5$
- $2 \le K \le N$
- $1 \le M \le \min(N,10^5)$
- $1 \le X_1 \lt X_2 \lt \cdots \lt X_M \le N$
入力
以下の形式で標準入力から与えられます。$N\ K\ M$ $X_1\ X_2\ \cdots \ X_M$
出力
$k=1,2,\cdots ,M$ について、$k$ 行目に、山の個数が $X_k$ になるまで操作した後得られるカード配置の個数を $998244353$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
5 3 4 1 2 3 5
出力
8 0 6 1
括弧が各山を、括弧内の数値が山のカード番号を上から順に表すとします。
例えば、(3,2,1),(4),(5)は、
左から $1$ 番目の山のカード番号が上から順に $3,2,1$ であり、
左から $2$ 番目、$3$ 番目の山はそれぞれカード $4$, $5$の一枚のみ、を表します。
初期配置は(1),(2),(3),(4),(5)です。
例えば次のように操作することで(3,2,1),(4),(5)になります。
- 長さ $3$ の連続部分列
(1),(2),(3)を選び、右が上になるよう重ねる。(1),(2),(3),(4),(5)→(3,2,1),(4),(5)
また、次のように操作することで(5,2,3,4,1)になります。
- 長さ $3$ の連続部分列
(2),(3),(4)を選び、左が上になるよう重ねる。(1),(2),(3),(4),(5)→(1),(2,3,4),(5) - 長さ $3$ の連続部分列
(1),(2,3,4),(5)を選び、右が上になるよう重ねる。(1),(2,3,4),(5)→(5,2,3,4,1)
山の個数が $X_1=1$ 個になるまで操作して得られるカード配置は、上記例の後者の場合を含め $8$ 個あります。
山の個数が $X_2=2$ 個になるまで操作して得られるカード配置は、$0$ 個です。
山の個数が $X_3=3$ 個になるまで操作して得られるカード配置は、上記例の前者の場合を含め $6$ 個あります。
山の個数が $X_4=5$ 個になるまで操作して得られるカード配置は、$1$ 個です。
サンプル2
入力
6 3 6 1 2 3 4 5 6
出力
0 20 0 8 0 1
サンプル3
入力
100000 10 5 1 10 100 1000 10000
出力
766720650 955984556 280937557 323992730 243114217
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。