#P13490. [ABC330G] Inversion Squared

    ID: 12674 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-指示变量期望线性性条件概率容斥原理一维前缀和增量维护模逆元

[ABC330G] Inversion Squared

AT_abc330_g [ABC330G] Inversion Squared

题目描述

给定一个长度为 NN 的数列 A=(A1,…,AN)A = (A_1, \ldots, A_N)。AA 的每个元素要么是 −1-1,要么是 11 到 NN 之间的整数,并且 11 到 NN 的每个整数在 AA 中最多出现一次。

对于 11 到 NN 的一个排列 P=(P1,…,PN)P = (P_1, \ldots, P_N),如果满足 Ai≠−1⇒Pi=AiA_i \neq -1 \Rightarrow P_i = A_i,则称 PP 为良好排列。请你求出所有良好排列的逆序数的平方和,并对 998244353998244353 取模。

排列 PP 的逆序数定义为满足 1≤i<j≤N1 \leq i < j \leq N 且 Pi>PjP_i > P_j 的整数对 (i,j)(i, j) 的个数。

输入格式

输入从标准输入读入,格式如下:

NN A1A_1 A2A_2 …\ldots ANA_N

输出格式

输出答案。

输入输出样例 #1

输入 #1

4
3 -1 2 -1

输出 #1

29

输入输出样例 #2

输入 #2

10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出 #2

952235647

输入输出样例 #3

输入 #3

15
-1 -1 10 -1 -1 -1 2 -1 -1 3 -1 -1 -1 -1 1

输出 #3

460544744

说明/提示

限制条件

  • 1≤N≤30001 \leq N \leq 3000
  • 1≤Ai≤N1 \leq A_i \leq N 或 Ai=−1A_i = -1
  • AA 中 1,…,N1, \ldots, N 每个数最多出现一次
  • 输入均为整数

样例解释 1

良好排列有 P=(3,1,2,4)P = (3, 1, 2, 4) 和 P=(3,4,2,1)P = (3, 4, 2, 1) 共 22 个,逆序数分别为 22 和 55。因此答案为 22+52=292^2 + 5^2 = 29。

样例解释 3

请对 998244353998244353 取模后输出答案。