H - EQual
問題文
あなたは競技プログラミングのオンサイトコンテストの予選を開こうとしてしています。
予選の参加者は $N$ 人おり、 $2X(\leq N)$ 人が決勝に進出します。
予選は以下の形式で行われます。
- $N$ 人の参加者は、2 回の「予選のコンテスト」に参加する。(この $N$ 人以外が「予選のコンテスト」に参加することはない)
- 1 回目の「予選のコンテスト」で上位 $X$ 人が決勝に進出する。
- まだ決勝進出の決まっていない参加者のうち、2 回目の「予選のコンテスト」での上位 $X$ 人が決勝に進出する。
なお、「予選のコンテスト」では、全ての参加者の順位が $1$ から $N$ の整数で決定され、異なる参加者が同じ順位を取ることはありません。
ここで、あなたは以下のように考えました。
「1 回目の予選のコンテストと 2 回目の予選のコンテストの問題が入れ替わった時に各参加者の順位もそのまま入れ替わるとする。この時、決勝に進出する参加者の集合が異なる場合、公平な予選ではないのではないか」
今 1 回目の「予選のコンテスト」で $i$ 位を取った人が、2 回目の「予選のコンテスト」で $Q_i$ 位を取ることがわかっています。
ただし、一部の参加者は順位を予想することができなかったので、その場合 $Q_i = -1$ とします。
順位が予想できた参加者は確実にその順位を取ります。
$Q_i = -1$ となる、 $i$ が $k$ 箇所の時、2回目の「予選のコンテスト」の順位としてあり得るものは、 $k!$ 通りあります。
整数 $N,X$ と数列 $Q = (Q_1, Q_2, \ldots, Q_N) $ が与えられるので、 $k!$ 通りの順位のうち、「1 回目の予選のコンテストと 2 回目の予選のコンテストの問題が入れ替わっても (つまり各参加者の 1 回目の予選のコンテストの順位と 2 回目の予選のコンテストの順位が入れ替わっても) 、決勝に進出する参加者の集合が変わらない順位」の総数を $998244353$ で割った余りを求めてください。
制約
- 入力は全て整数
- $2 \leq N \leq 5000$
- $1 \leq X $
- $ 2X \leq N $
- $Q_i \neq -1 \Rightarrow 1\leq Q_i \leq N$ ($1 \leq i \leq N$)
- $Q_i \neq -1$ かつ $Q_j \neq -1 \Rightarrow Q_i \neq Q_j$ ($1 \leq i < j \leq N$)
入力
入力は以下の形式で標準入力から与えられます。
$N$ $X$
$Q_1$ $Q_2$ $\ldots$ $Q_N$
出力
答えを 1 行に出力してください。
3 1
-1 1 -1
2
(元々の) 1 回目のコンテストで順位 $i$ を取った人を 人 $i$ と書きます。
$Q$ として、あり得るものは $(2,1,3)$ と $(3,1,2)$ の 2 通りですが、この 2 通り両方について、1 回目のコンテストと 2 回目のコンテストの問題が入れ替わっても、入れ替わらなくても人 1 と人 2 が決勝に進みます。
2 通りとも条件を満たすので、2
を出力します。
4 1
2 1 4 3
1
このケースでは、2 回目のコンテストで、誰が何位を取るのか完全にわかっています。
コンテストが入れ替わっても入れ替わらなくても、(元々の) 1 回目のコンテストで、1 位の人と 2 位の人の二人が決勝に進出します。
8 3
1 -1 -1 -1 -1 -1 -1 8
284
例えば$Q = (1,7,6,5,4,3,2,8)$ のケースを考えます。以下では、(元々の) 1回目のコンテストで、$i$ 位を取った人を人 $i$ と表記します。また、(元々の) 1回目のコンテストを予選A, (元々の) 2回目のコンテストを予選Bと表記します。
予選A→予選Bという順番で予選が実施された場合、予選Aで決勝に進出するのは人1,人2,人3です。 予選Bで決勝に進出するのは人5, 人6, 人7 です。
予選B→予選Aという順番で予選が実施された場合、予選Bで決勝に進出するのは人1,人6,人7 です。 予選Aで決勝に進出する人は人2, 人3, 人4です。
このようなケースは、コンテストを行う順番によって、決勝に進出する人が変わるため、公平な予選ではありません。
$Q$としてあり得るものは 720通りですが、このうち284通りが公平な予選になります。