問題一覧 > 通常問題

No.3650 Teleportation Cycles

レベル : / AI推定難易度 : 450 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 74
作問者 : Rino-program / テスター : gomaazarasi 👑 p-adic とある理系大学生の日常
お気に入りにしたユーザー ProblemId : 13691 / 自分の提出
問題文最終更新日: 2026-07-23 20:35:35
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 511 (Div.2) (順位表) の他の問題:

Problem Statement

There are $N$ cities, numbered from city $1$ to city $N$.

Each city $i$ has $1$ teleporter installed, which, when used, instantly moves you one-way to city $A_i$. Note that a teleporter may lead to the same city.

Find how many "simple cycles (round-trip routes)" exist, in which you travel through some cities by teleporters and return to the original city.
Note that a round-trip route consisting of only one city (the case where moving from that city returns to the same city) also counts as one route.
More precisely, find the number of sets $S$ of cities satisfying the following conditions.

  • The number of cities contained in $S$ is at least $1$.
  • For any city $v$ contained in $S$, the teleporter's destination $A_v$ is also contained in $S$.
  • Starting from any city contained in $S$, you can visit every city contained in $S$ exactly once and return to the original city.

Constraints

  • $2 \le N \le 2 \times 10^5$
  • $1 \le A_i \le N$
  • All input values are integers.

Input

The input is given from standard input in the following format.

$N$
$A_1 \ A_2 \ \dots \ A_N$

Output

Output the number of existing round-trip routes (cycles) as an integer.
Print a newline at the end.

Sample

Sample 1
Input
4
2 3 1 4
Output
2

There is $1$ round-trip route of length $3$, cities $1 \to 2 \to 3 \to 1$,
and $1$ round-trip route of length $1$, city $4 \to 4$,
for a total of $2$.

Sample 2
Input
5
2 3 4 5 2
Output
1

Sample 3
Input
6
2 3 1 5 6 4
Output
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。