← 返回题目列表

AtCoder · arc187_c

C. 1 循环冒泡排序

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

分数: 800 点

问题陈述

对于排列 P = (P_1, \ldots, P_N) of (1, \ldots, N),让 P' = (P'_1, \ldots, P'_N) 是执行一次以下操作得到的排列。

  • 对于 i = 1, 2, \ldots, N-1 按此顺序,如果 P_i > P_{i+1},交换 P_i 和 P_{i+1}.

给你一个序列 Q = (Q_1, \ldots, Q_N) 长度 N。每个 Q_i is -1 或之间的整数 1 和 N,包括在内。

求模数 998244353,排列 P of (1, \ldots, N) 这样,对于每个 i,如果 Q_i \neq -1 然后 Q_i = P'_i.

约束

  • 所有输入数字均为整数。
  • 2 \leq N \leq 5000
  • 每个 Q_i is -1 或之间的整数 1 和 N.
  • 每个 1,2,\ldots,N 最多出现一次 Q.

输入

输入由标准输入按以下格式给出:

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 满足条件:

  • (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.