#P13697. [ARC118E] Avoid Permutations

    ID: 12899 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-容斥原理网格 DP计数 DP滚动数组排列数计算

[ARC118E] Avoid Permutations

题目描述

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

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

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

给定正整数 NN 以及整数序列 A=(A1,A2,…,AN)A = (A_1, A_2, \ldots, A_N)。每个 AiA_i 要么为 −1-1,要么为 11 到 NN 之间的整数。

我们考虑所有满足 Ai≠−1  ⟹  Pi=AiA_i \neq -1 \implies P_i = A_i 的 (1,2,…,N)(1, 2, \ldots, N) 的排列 P=(P1,P2,…,PN)P = (P_1, P_2, \ldots, P_N)。对于所有这样的 PP,求 ∑f(P)\sum f(P),并对 998244353998244353 取模。

输入格式

输入为一行,格式如下:

NN A1A_1 A2A_2 …\ldots ANA_N

输出格式

输出答案。

输入输出样例 #1

输入 #1

4
1 -1 4 -1

输出 #1

41

输入输出样例 #2

输入 #2

4
4 3 2 1

输出 #2

2

输入输出样例 #3

输入 #3

3
-1 -1 -1

输出 #3

48

说明/提示

数据范围

  • 1≤N≤2001 \leq N \leq 200
  • Ai=−1A_i = -1 或 1≤Ai≤N1 \leq A_i \leq N
  • 对于 i≠ji \neq j,若 Ai≠−1A_i \neq -1 且 Aj≠−1A_j \neq -1,则 Ai≠AjA_i \neq A_j

样例解释 1

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

  ......         ......
  .#....         .#....
  ..#...         ...#..
  ....#.         ....#.
  ...#..         ..#...
  ......         ......
P=(1,2,4,3)    P=(1,3,4,2)
  • 对于排列 P=(1,2,4,3)P = (1, 2, 4, 3),有 f(P)=18f(P) = 18。
  • 对于排列 P=(1,3,4,2)P = (1, 3, 4, 2),有 f(P)=23f(P) = 23。

它们的和 4141 即为答案。

样例解释 2

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

样例解释 3

  • 对于排列 P=(1,2,3)P = (1, 2, 3),有 f(P)=10f(P) = 10。
  • 对于排列 P=(1,3,2)P = (1, 3, 2),有 f(P)=6f(P) = 6。
  • 对于排列 P=(2,1,3)P = (2, 1, 3),有 f(P)=6f(P) = 6。
  • 对于排列 P=(2,3,1)P = (2, 3, 1),有 f(P)=12f(P) = 12。
  • 对于排列 P=(3,1,2)P = (3, 1, 2),有 f(P)=12f(P) = 12。
  • 对于排列 P=(3,2,1)P = (3, 2, 1),有 f(P)=2f(P) = 2。

它们的和 4848 即为答案。

由 ChatGPT 4.1 翻译