← 返回题目列表

AtCoder · abc330_g

G. 平方反演

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

分数: 625 点

问题陈述

给你一个序列 A = (A_1,\ldots,A_N) 长度 N。的每个元素 A 是 -1 或之间的整数 1 和 N,以及来自的每个整数 1 to N 最多包含一次。

排列 P=(P_1,\ldots,P_N) of (1,\ldots,N) 被称为 良好的排列 当且仅当满足 A_i \neq -1 \Rightarrow P_i = A_i。求所有好的排列的反转数的平方和,模 998244353.

排列的反转数 P 是整数对的数量 (i,j) 这样 1\leq i < j \leq N 和 P_i > P_j.

约束

  • 1\leq N\leq 3000
  • A_i = -1 or 1\leq A_i \leq N.
  • 每个整数 1 to N 最多包含一次 A.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N 
A_1 \ldots A_N

输出

打印答案。


示例输入 1

4
3 -1 2 -1

示例输出 1

29

有两种好的排列: P=(3,1,2,4) 和 P=(3,4,2,1),带有反转数 2 和 5。

因此,答案是 2^2 + 5^2 = 29.


示例输入 2

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

示例输出 2

952235647

示例输入 3

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

示例输出 3

460544744

求总和模 998244353.