/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
(1,\ldots,N) の順列 P=(P_1,\ldots,P_N) に対して，以下の操作を一度行うことにより得られる順列を P'=(P'_1,\ldots,P'_N) とします．
- i=1,2,\ldots,N-1 の順に，P_i>P_{i+1} ならば P_i と P_{i+1} を入れ替える．
長さ N の数列 Q=(Q_1,\ldots,Q_N) が与えられます． Q_i は -1 または 1 以上 N 以下の整数 です．
全ての i について Q_i\neq -1 ならば Q_i=P'_i を満たすような (1,\ldots,N) の順列 P の個数を 998244353 で割ったあまりを求めてください．
制約
- 入力される数値は全て整数
- 2 \leq N \leq 5000
- Q_i は -1 または 1 以上 N 以下の整数
- Q に 1,2,\ldots,N が含まれる個数はそれぞれ 1 個以下
入力
入力は以下の形式で標準入力から与えられる．
N Q_1 \ldots Q_N
出力
答えを出力せよ．
入力例 1
4 -1 -1 2 4
出力例 1
6
例えば P=(3,1,4,2) は条件を満たします．これは以下の操作の挙動から確認できます．
- i=1 のとき，P_1 > P_2 なので P_1 と P_2 を入れ替え，P=(1,3,4,2) となる．
- i=2 のとき，P_2 < P_3 なので 何もしない．
- i=3 のとき，P_3 > P_4 なので P_3 と P_4 を入れ替え，P=(1,3,2,4) となる．
- 以上より P'=(1,3,2,4) となり，P'_3=2,P'_4=4 を満たす．
条件を満たす P は以下の 6 個です．
- (1,3,4,2)
- (1,4,3,2)
- (3,1,4,2)
- (3,4,1,2)
- (4,1,3,2)
- (4,3,1,2)
入力例 2
6 -1 -1 -1 -1 2 -1
出力例 2
120
入力例 3
15 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 7 -1 -1 -1 -1
出力例 3
237554682
個数を 998244353 で割ったあまりを求めることに注意してください．
Score : 800 points
Problem Statement
For a permutation P = (P_1, \ldots, P_N) of (1, \ldots, N), let P' = (P'_1, \ldots, P'_N) be the permutation obtained by performing the following operation once.
- For i = 1, 2, \ldots, N-1 in this order, if P_i > P_{i+1}, swap P_i and P_{i+1}.
You are given a sequence Q = (Q_1, \ldots, Q_N) of length N. Each Q_i is -1 or an integer between 1 and N, inclusive.
Find the number, modulo 998244353, of permutations P of (1, \ldots, N) such that, for every i, if Q_i \neq -1 then Q_i = P'_i.
Constraints
- All input numbers are integers.
- 2 \leq N \leq 5000
- Each Q_i is -1 or an integer between 1 and N.
- Each of 1,2,\ldots,N appears at most once in Q.
Input
The input is given from Standard Input in the following format:
N Q_1 \ldots Q_N
Output
Print the answer.
Sample Input 1
4 -1 -1 2 4
Sample Output 1
6
For example, P = (3,1,4,2) satisfies the conditions. This can be confirmed by the following behavior of the operation.
- For i=1, since P_1 > P_2, swap P_1 and P_2, resulting in P = (1,3,4,2).
- For i=2, since P_2 < P_3, do nothing.
- For i=3, since P_3 > P_4, swap P_3 and P_4, resulting in P = (1,3,2,4).
- Thus, P' = (1,3,2,4), satisfying P'_3=2 and P'_4=4.
There are six permutations P that satisfy the conditions:
- (1,3,4,2)
- (1,4,3,2)
- (3,1,4,2)
- (3,4,1,2)
- (4,1,3,2)
- (4,3,1,2)
Sample Input 2
6 -1 -1 -1 -1 2 -1
Sample Output 2
120
Sample Input 3
15 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 7 -1 -1 -1 -1
Sample Output 3
237554682
Remember to find the count modulo 998244353.