← 返回题目列表

AtCoder · arc118_e

E. 避免排列

中文机器翻译题面 查看原题

分数: 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.