D - One to One Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

全ての要素が 1 以上 N 以下である長さ N の整数列 X=(X_1,X_2,\dots,X_N) に対して次の問題を考え、その答えを f(X) とします。

N 頂点の無向グラフ G があります。(G は多重辺や自己ループを含むことがあります。) G の辺は N 本あり、そのうち i 番目の辺は頂点 i と頂点 X_i を繋ぐ辺です。G の連結成分の個数を求めてください。

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。各 A_i は 1 以上 N 以下の整数あるいは -1 です。

全ての要素が 1 以上 N 以下である長さ N の整数列 X=(X_1,X_2,\dots,X_N) であって、A_i \neq -1 \Rightarrow A_i = X_i を満たすものを考えます。そのような全ての X に対する f(X) の総和を 998244353 で割ったあまりを求めてください。

制約

  • 1 \le N \le 2000
  • A_i は 1 以上 N 以下あるいは -1 である。
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3
-1 1 3

出力例 1

5

X として条件を満たすものは以下の 3 通りがあります。

  • X=(1,1,3) の時、問題の答えは 2 です。
  • X=(2,1,3) の時、問題の答えは 2 です。
  • X=(3,1,3) の時、問題の答えは 1 です。

よって答えは 2+2+1=5 です。

入力例 2

1
1

出力例 2

1

入力例 3

8
-1 3 -1 -1 8 -1 -1 -1

出力例 3

433760

Score : 700 points

Problem Statement

For an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N (inclusive), consider the question below, and let f(X) be the answer.

There is an undirected graph G with N vertices (and possibly multi-edges and self-loops). G has N edges, the i-th of which connects Vertex i and Vertex X_i. Find the number of connected components in G.

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N, where each A_i is an integer between 1 and N (inclusive) or -1.

Consider an integer sequence X=(X_1,X_2,\dots,X_N) of length N whose elements are all between 1 and N such that A_i \neq -1 \Rightarrow A_i = X_i. Find the sum of f(X) over all such X, modulo 998244353.

Constraints

  • 1 \le N \le 2000
  • A_i is between 1 and N (inclusive) or -1.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Prin the answer.

Sample Input 1

3
-1 1 3

Sample Output 1

5

There are three sequences X satisfying the requirement, as follows.

  • X=(1,1,3), for which the answer to the question is 2.
  • X=(2,1,3), for which the answer to the question is 2.
  • X=(3,1,3), for which the answer to the question is 1.

Thus, the answer is 2+2+1=5.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

8
-1 3 -1 -1 8 -1 -1 -1

Sample Output 3

433760