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 翻译