分数: 600 点
问题陈述
给定的是一个序列 a_1,\dots,a_n 组成 1,\dots, n 和 -1,以及一个整数 d。 有多少个序列 p_1,\dots,p_n 满足以下条件吗? 打印计数模数 998244353.
- p_1,\dots,p_n 是一个排列 1,\dots, n.
- 对于每个 i=1,\dots,n, a_i=p_i if a_i\neq -1。 (也就是说, p_1,\dots,p_n 可以通过替换来获得 -1位于 a_1,\dots,a_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 or a_i=-1.
- |a_i-i|\le d if a_i\neq -1.
- a_i\neq a_j,如果 i\neq j 和 a_i, a_j \neq -1.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
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,2,3,4,5 可以通过替换获得 -1 is (2,3,4,5,1),其第五项违反了条件,所以答案是 0.
示例输入 3
16 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
示例输出 3
794673086
打印计数模数 998244353.