/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 N が与えられます． 長さ N の整数列 x=(x_1,x_2,\cdots,x_N) は，以下の条件を満たすとき（そしてそのときのみ）よい数列と呼ばれます．
- x の各要素は 1 以上 N 以下の整数である．
- 各整数 i (1 \leq i \leq N) に対し，i が i+1 個以上連続して並ぶような場所が x 内に存在しない．
長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． A の各要素は 1 以上 N 以下の整数もしくは -1 です． それぞれの -1 を 1 以上 N 以下の整数に置き換えることで得られるよい数列の個数を 998244353 で割ったあまりを求めてください．
制約
- 1 \leq N \leq 5000
- A_i=-1 もしくは 1 \leq A_i \leq N
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N A_1 A_2 \cdots A_N
出力
答えを出力せよ．
入力例 1
2 -1 -1
出力例 1
3
それぞれの -1 を 1 以上 2 以下の整数で置き換えて得られる数列は 4 通りあります．
ここで A=(1,1) について考えると，1 が 2 個連続してしまうためよい数列ではありません．
それ以外の A=(1,2),(2,1),(2,2) について考えると，これらはすべてよい数列です．
よって答えは 3 です．
入力例 2
3 2 -1 2
出力例 2
2
入力例 3
4 -1 1 1 -1
出力例 3
0
入力例 4
20 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1
出力例 4
128282166
Score : 600 points
Problem Statement
You are given an integer N. An integer sequence x=(x_1,x_2,\cdots,x_N) of length N is called a good sequence if and only if the following conditions are satisfied:
- Each element of x is an integer between 1 and N, inclusive.
- For each integer i (1 \leq i \leq N), there is no position in x where i appears i+1 or more times in a row.
You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Each element of A is -1 or an integer between 1 and N. Find the number, modulo 998244353, of good sequences that can be obtained by replacing each -1 in A with an integer between 1 and N.
Constraints
- 1 \leq N \leq 5000
- A_i=-1 or 1 \leq A_i \leq N.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
2 -1 -1
Sample Output 1
3
You can obtain four sequences by replacing each -1 with an integer between 1 and 2.
A=(1,1) is not a good sequence because 1 appears twice in a row.
The other sequences A=(1,2),(2,1),(2,2) are good.
Thus, the answer is 3.
Sample Input 2
3 2 -1 2
Sample Output 2
2
Sample Input 3
4 -1 1 1 -1
Sample Output 3
0
Sample Input 4
20 9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1
Sample Output 4
128282166