← 返回题目列表

AtCoder · nomura2020_d

D. 城市规划

中文机器翻译题面 查看原题

分数: 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