/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
1,\dots, n と -1 からなる数列 a_1,\dots,a_n と整数 d が与えられます。 以下の条件を満たす数列 p_1,\dots,p_n はいくつありますか？ 答えを 998244353 で割ったあまりを出力してください。
- p_1,\dots,p_n は 1,\dots, n の順列
- i=1,\dots,n について、 a_i\neq -1 ならば a_i=p_i （つまり、a_1,\dots,a_n の -1 の項を適切に置き換えることで p_1,\dots,p_n に書き換えできる）
- i=1,\dots,n について、 |p_i - i|\le d
制約
- 1 \le d \le 5
- d < n \le 500
- 1\le a_i \le n または a_i=-1
- a_i\neq -1 ならば |a_i-i|\le d
- i\neq j かつ a_i, a_j \neq -1 ならば a_i\neq a_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
n d a_1 \dots a_n
出力
条件を満たす数列の数を 998244353 で割ったあまりを出力せよ。
入力例 1
4 2 3 -1 1 -1
出力例 1
2
(3,2,1,4) と (3,4,1,2) が条件を満たします。
入力例 2
5 1 2 3 4 5 -1
出力例 2
0
-1 を置き換えて得られる 1,2,3,4,5 の順列は (2,3,4,5,1) のみです。 この順列は、5 項目が条件を満たさないため、答えは 0 です。
入力例 3
16 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
出力例 3
794673086
998244353 で割ったあまりを出力してください。
Score : 600 points
Problem Statement
Given is a sequence a_1,\dots,a_n consisting of 1,\dots, n and -1, along with an integer d. How many sequences p_1,\dots,p_n satisfy the conditions below? Print the count modulo 998244353.
- p_1,\dots,p_n is a permutation of 1,\dots, n.
- For each i=1,\dots,n, a_i=p_i if a_i\neq -1. (That is, p_1,\dots,p_n can be obtained by replacing the -1s in a_1,\dots,a_n in some way.)
- For each i=1,\dots,n, |p_i - i|\le d.
Constraints
- 1 \le d \le 5
- d < n \le 500
- 1\le a_i \le n or a_i=-1.
- |a_i-i|\le d if a_i\neq -1.
- a_i\neq a_j, if i\neq j and a_i, a_j \neq -1.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
n d a_1 \dots a_n
Output
Print the number of sequences that satisfy the conditions, modulo 998244353.
Sample Input 1
4 2 3 -1 1 -1
Sample Output 1
2
The conditions are satisfied by (3,2,1,4) and (3,4,1,2).
Sample Input 2
5 1 2 3 4 5 -1
Sample Output 2
0
The only permutation of 1,2,3,4,5 that can be obtained by replacing the -1 is (2,3,4,5,1), whose fifth term violates the condition, so the answer is 0.
Sample Input 3
16 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 3
794673086
Print the count modulo 998244353.