/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
長さ N の数列 A = (A_1,\ldots,A_N) が与えられます。 A の各要素は -1 または 1 以上 N 以下の整数で、かつ 1 から N までの整数はそれぞれ高々 1 個含まれます。
(1,\ldots,N) の順列 P=(P_1,\ldots,P_N) であって、 A_i \neq -1 \Rightarrow P_i = A_i を満たすものを 良い順列 と呼びます。良い順列全てに対する、転倒数の二乗の総和を 998244353 で割ったあまりを求めてください。
なお、順列 P の転倒数は、 1\leq i < j \leq N と P_i > P_j を共に満たすような整数の組 (i,j) の個数です。
制約
- 1\leq N\leq 3000
- 1\leq A_i \leq N または A_i = -1
- A に 1,\ldots,N はそれぞれ高々 1 個含まれる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 つで、転倒数はそれぞれ 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 で割ったあまりを求めてください。
Score : 625 points
Problem Statement
You are given a sequence A = (A_1,\ldots,A_N) of length N. Each element of A is either -1 or an integer between 1 and N, and each integer from 1 to N is contained at most once.
A permutation P=(P_1,\ldots,P_N) of (1,\ldots,N) is called a good permutation if and only if it satisfies A_i \neq -1 \Rightarrow P_i = A_i. Find the sum of the squares of the inversion numbers of all good permutations, modulo 998244353.
The inversion number of a permutation P is the number of pairs of integers (i,j) such that 1\leq i < j \leq N and P_i > P_j.
Constraints
- 1\leq N\leq 3000
- A_i = -1 or 1\leq A_i \leq N.
- Each integer from 1 to N is contained at most once in A.
- All input values are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
4 3 -1 2 -1
Sample Output 1
29
There are two good permutations: P=(3,1,2,4) and P=(3,4,2,1), with inversion numbers 2 and 5, respectively.
Thus, the answer is 2^2 + 5^2 = 29.
Sample Input 2
10 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2
952235647
Sample Input 3
15 -1 -1 10 -1 -1 -1 2 -1 -1 3 -1 -1 -1 -1 1
Sample Output 3
460544744
Find the sum modulo 998244353.