题目描述

$(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$ 以下の整数です。

$(1,\ 2,\ \ldots,\ N)$ の順列 $P\ =\ (P_1,\ P_2,\ \ldots,\ P_N)$ であって、$A_i\neq\ -1\ \implies\ P_i\ =\ A_i$ を満たすものを考えます。そのようなすべての $P$ に対する $f(P)$ の総和を、$998244353$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

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

输出格式

答えを出力してください。

题目大意

对于一个排列 $P$，定义 $F(P)$ 如下：

对于一个 $(N+2)\times (N+2)$ 的网格图，行列标号为 $0\sim N+1$，从 $(0,0)$ 走到 $(N+1,N+1)$ 在不经过 $(i,P_i)$ 情况下的方案数。

给定一个残缺的排列，对于其所有补全求函数之和。

translated by cszyf

4
1 -1 4 -1

41

4
4 3 2 1

2

3
-1 -1 -1

48

提示

制約

• $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$

Sample Explanation 1

$2$ つの順列 $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$ が答えとなります。

Sample Explanation 2

この例では、計算対象となる順列 $P$ は $P\ =\ (4,3,2,1)$ のひとつです。

Sample Explanation 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$ が答えとなります。