/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
1, 2, \cdots, N の番号がついた N 個の町があります。
現在、2 つの相異なる町を双方向に結ぶ道をいくつか作ることが計画されています。現時点では、町を結ぶ道はありません。
この計画において、各町は他の町を 1 つ選んで、道を 1 本以上使ってその町に移動できるように要請します。
N 個の町の要請は配列 P_1, P_2, \cdots, P_N で表され、町 i の要請は、P_i = -1 のときまだ決定されていないこと、1 \leq P_i \leq N であるとき町 P_i を選んだことを表します。
P_i = -1 である町の個数を K 個としたとき、全体では (N-1)^K 通りの要請方法が考えられます。それぞれの要請方法について、すべての町の要請を満たすために作る必要がある道の本数の最小値を求め、その総和を 10^9+7 で割った余りを出力してください。
制約
- 2 \leq N \leq 5000
- P_i = -1 または 1 \leq P_i \leq N
- P_i \neq i
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \cdots P_N
出力
それぞれの要請方法について、すべての町の要請を満たすために作る必要がある道の本数の最小値を求め、その総和を 10^9+7 で割った余りを出力せよ。
入力例 1
4 2 1 -1 3
出力例 1
8
要請方法としては次の 3 通りがあります。
- P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3 とする。このとき、例えば道 (1,2),(1,3),(3,4) の 3 つを作ることですべての町の要請を満たすことができ、これが最小です。
- P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3 とする。このとき、例えば道 (1,2),(1,3),(3,4) の 3 つを作ることですべての町の要請を満たすことができ、これが最小です。
- P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3 とする。このとき、例えば道 (1,2),(3,4) の 2 つを作ることですべての町の要請を満たすことができ、これが最小です。
必ずしも町 i と町 P_i が直接繋がっている必要がないことに注意してください。
よって、総和は 8 です。
入力例 2
2 2 1
出力例 2
1
初めから要請が 1 通りに決まっている場合もあります。
入力例 3
10 2 6 9 -1 6 9 -1 -1 -1 -1
出力例 3
527841
Score : 700 points
Problem Statement
There are N towns numbered 1, 2, \cdots, N.
Some roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns.
In the planning of construction, each town chooses one town different from itself and requests the following: roads are built so that the chosen town is reachable from itself using one or more roads.
These requests from the towns are represented by an array P_1, P_2, \cdots, P_N. If P_i = -1, it means that Town i has not chosen the request; if 1 \leq P_i \leq N, it means that Town i has chosen Town P_i.
Let K be the number of towns i such that P_i = -1. There are (N-1)^K ways in which the towns can make the requests. For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).
Constraints
- 2 \leq N \leq 5000
- P_i = -1 or 1 \leq P_i \leq N.
- P_i \neq i
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_1 P_2 \cdots P_N
Output
For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).
Sample Input 1
4 2 1 -1 3
Sample Output 1
8
There are three ways to make requests, as follows:
- Choose P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.
- Choose P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.
- Choose P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3. In this case, at least two roads - for example, (1,2),(3,4) - are needed to meet the requests.
Note that it is not mandatory to connect Town i and Town P_i directly.
The sum of the above numbers is 8.
Sample Input 2
2 2 1
Sample Output 2
1
There may be just one fixed way to make requests.
Sample Input 3
10 2 6 9 -1 6 9 -1 -1 -1 -1
Sample Output 3
527841