AT_arc118_e.[ARC118E] Avoid Permutations

对于 $(1, 2, \ldots, N)$ 的一个排列 $P = (P_1, P_2, \ldots, P_N)$，我们考虑如下问题，并将其答案记作 $f(P)$。

有一个 $(N+2)\times (N+2)$ 的格子，行号从上到下依次为 $0, 1, \ldots, N+1$，列号从左到右依次为 $0, 1, \ldots, N+1$。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

从 $(0, 0)$ 出发，每次只能向右或向下移动到相邻的格子，最终到达 $(N+1, N+1)$。但对于所有 $1\leq i\leq N$，格子 $(i, P_i)$ 不允许经过。问这样的路径有多少条？

给定正整数 $N$ 以及整数序列 $A = (A_1, A_2, \ldots, A_N)$。每个 $A_i$ 要么为 $-1$，要么为 $1$ 到 $N$ 之间的整数。

我们考虑所有满足 $A_i \neq -1 \implies P_i = A_i$ 的 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$。对于所有这样的 $P$，求 $\sum f(P)$，并对 $998244353$ 取模。

输入为一行，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出答案。

数据范围

• $1 \leq N \leq 200$
• $A_i = -1$ 或 $1 \leq A_i \leq N$
• 对于 $i \neq j$，若 $A_i \neq -1$ 且 $A_j \neq -1$，则 $A_i \neq A_j$

样例解释 1

有两个排列 $P = (1, 2, 4, 3)$ 和 $P = (1, 3, 4, 2)$，需要分别计算 $f(P)$ 并求和。对于每个 $P$，在格子中不可经过的格子如下（可经过用 . 表示，不可经过用 # 表示）：

  ......         ......
  .#....         .#....
  ..#...         ...#..
  ....#.         ....#.
  ...#..         ..#...
  ......         ......
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

本例中，唯一满足条件的排列为 $P = (4, 3, 2, 1)$。

样例解释 3

• 对于排列 $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$ 即为答案。

由 ChatGPT 4.1 翻译