分数: 700 点
问题陈述
有 N 城镇编号 1, 2, \cdots, N.
计划修建一些道路,使每条道路双向连接两个不同的城镇。目前,没有连接城镇的道路。
在建设规划中,每个城镇选择一个与自己不同的城镇,并提出以下要求:修建道路,使所选城镇可通过一条或多条道路到达。
这些来自城镇的请求由一个数组表示 P_1, P_2, \cdots, P_N。如果 P_i = -1,表示城镇 i 尚未选择该请求;如果 1 \leq P_i \leq N,表示城镇 i 已选择城镇 P_i.
让 K 是城镇数量 i 这样 P_i = -1。有 (N-1)^K 城镇提出请求的方式。对于每种提出请求的方式,找到满足所有请求所需的最少道路数量,并打印这些道路的总和 (N-1)^K 数字,模 (10^9+7).
约束
- 2 \leq N \leq 5000
- P_i = -1 or 1 \leq P_i \leq N.
- P_i \neq i
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P_1 P_2 \cdots P_N
输出
对于每种提出请求的方式,找到满足所有请求所需的最少道路数,并打印这些道路的总和 (N-1)^K 数字,模 (10^9+7).
示例输入 1
4 2 1 -1 3
示例输出 1
8
提出请求的方式有以下三种:
- 选择 P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3。在这种情况下,至少有 3 条道路 - 例如, (1,2),(1,3),(3,4) - 需要满足请求。
- 选择 P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3。在这种情况下,至少有 3 条道路 - 例如, (1,2),(1,3),(3,4) - 需要满足请求。
- 选择 P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3。在这种情况下,至少有两条路 - 例如, (1,2),(3,4) - 需要满足请求。
请注意,连接城镇不是强制性的 直接 i 和镇 P_i 。
上述数字的总和是 8.
示例输入 2
2 2 1
示例输出 2
1
可能只有一种固定的方式来提出请求。
示例输入 3
10 2 6 9 -1 6 9 -1 -1 -1 -1
示例输出 3
527841