分数: 800 点
问题陈述
让我们考虑下面的排列问题 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N),并将答案表示为 f(P).
我们有一个 (N+2)\times (N+2) 网格,其中行已编号 0, 1, \ldots, N+1 从上到下,各列已编号 0, 1, \ldots, N+1 从左到右。让 (i,j) 表示位于 i第行和 j- 第列。
考虑来自 (0, 0) to (N+1, N+1) 我们反复向右移动一格或向下移动一格。然而,对于每个 1\leq i\leq N,我们不能参观广场 (i, P_i)。这样的路径有多少条?
给你一个正整数 N 和一个整数序列 A = (A_1, A_2, \ldots, A_N),其中每个 A_i is -1 或之间的整数 1 和 N (含)。
考虑所有排列 P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) 满意 A_i\neq -1 \implies P_i = A_i。求总和 f(P) 综上所述 P,模数 998244353.
约束
- 1\leq N\leq 200
- A_i = -1 or 1\leq A_i\leq N.
- A_i\neq A_j if A_i\neq -1 和 A_j\neq -1,对于 i\neq j.
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
4 1 -1 4 -1
示例输出 1
41
我们想要找到的总和 f(P) 超过两种排列 P = (1,2,4,3) 和 P = (1,3,4,2)。下图显示了它们各自的不可通行的方格,其中 . 和 # 分别代表可通行和不可通行的方块。
...... ...... .#.... .#.... ..#... ...#.. ....#. ....#. ...#.. ..#... ...... ...... P=(1,2,4,3) P=(1,3,4,2)
- 对于 P = (1,2,4,3),我们有 f(P) = 18.
- 对于 P = (1,3,4,2),我们有 f(P) = 23.
答案是它们的总和: 41.
示例输入 2
4 4 3 2 1
示例输出 2
2
在此示例中,我们要计算 f(P) 仅用于一种排列 P = (4,3,2,1).
示例输入 3
3 -1 -1 -1
示例输出 3
48
- 对于 P = (1,2,3),我们有 f(P) = 10.
- 对于 P = (1,3,2),我们有 f(P) = 6.
- 对于 P = (2,1,3),我们有 f(P) = 6.
- 对于 P = (2,3,1),我们有 f(P) = 12.
- 对于 P = (3,1,2),我们有 f(P) = 12.
- 对于 P = (3,2,1),我们有 f(P) = 2.
答案是它们的总和: 48.