/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
(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 で割った余りを求めてください。
制約
- 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
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \ldots A_N
出力
答えを出力してください。
入力例 1
4 1 -1 4 -1
出力例 1
41
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 が答えとなります。
入力例 2
4 4 3 2 1
出力例 2
2
この例では、計算対象となる順列 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 が答えとなります。
Score : 800 points
Problem Statement
Let us consider the problem below for a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N), and denote the answer by f(P).
We have an (N+2)\times (N+2) grid, where the rows are numbered 0, 1, \ldots, N+1 from top to bottom and the columns are numbered 0, 1, \ldots, N+1 from left to right. Let (i,j) denote the square at the i-th row and j-th column.
Consider paths from (0, 0) to (N+1, N+1) where we repeatedly move one square right or one square down. However, for each 1\leq i\leq N, we must not visit the square (i, P_i). How many such paths are there?
You are given a positive integer N and an integer sequence A = (A_1, A_2, \ldots, A_N), where each A_i is -1 or an integer between 1 and N (inclusive).
Consider all permutations P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N) satisfying A_i\neq -1 \implies P_i = A_i. Find the sum of f(P) over all such P, modulo 998244353.
Constraints
- 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 and A_j\neq -1, for i\neq j.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 1 -1 4 -1
Sample Output 1
41
We want to find the sum of f(P) over two permutations P = (1,2,4,3) and P = (1,3,4,2). The figure below shows the impassable squares for each of them, where . and # represent a passable and impassable square, respectively.
...... ...... .#.... .#.... ..#... ...#.. ....#. ....#. ...#.. ..#... ...... ...... P=(1,2,4,3) P=(1,3,4,2)
- For P = (1,2,4,3), we have f(P) = 18.
- For P = (1,3,4,2), we have f(P) = 23.
The answer is the sum of them: 41.
Sample Input 2
4 4 3 2 1
Sample Output 2
2
In this sample, we want to compute f(P) for just one permutation P = (4,3,2,1).
Sample Input 3
3 -1 -1 -1
Sample Output 3
48
- For P = (1,2,3), we have f(P) = 10.
- For P = (1,3,2), we have f(P) = 6.
- For P = (2,1,3), we have f(P) = 6.
- For P = (2,3,1), we have f(P) = 12.
- For P = (3,1,2), we have f(P) = 12.
- For P = (3,2,1), we have f(P) = 2.
The answer is the sum of them: 48.