[ABC357] E - Reachability in Functional Graph

E - Reachability in Functional Graph

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 450 分

题面

有一个有 个顶点编号为 到 的有向图，有 条边。
每个顶点的出度为 ，从顶点 出发的边指向顶点 。
计算顶点对 的数量，使得从顶点 可到达顶点 。

这里，如果存在长度为 的顶点序列 满足以下条件，则顶点 可从顶点 到达。
特别地，当 时，总是可到达。

• 。
• 。
• 对于每个 ，存在一条边从顶点 指向顶点 。

限制条件

• 所有输入均为整数。

---

输入

从标准输入中以以下格式给出输入：

输出

输出顶点对 的数量，使得顶点 可从顶点 到达。

---

输入样例 1

4
2 1 1 4

输出样例 1

8

从顶点 可到达的顶点有 。
从顶点 可到达的顶点有 。
从顶点 可到达的顶点有 。
从顶点 可到达的顶点是 。
因此，顶点对 的数量使得顶点 可从顶点 到达为 。
注意顶点 的边是一个自环，即指向顶点 本身。

---

输入样例 2

5
2 4 3 1 2

输出样例 2

14

---

输入样例 3

10
6 10 4 1 5 9 8 6 5 1

输出样例 3

41