← 返回题目列表

AtCoder · arc132_c

C. 几乎已排序

中文机器翻译题面 查看原题

分数: 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.