実行時間制限: 2 sec / メモリ制限: 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