/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。ここで、各 A_i (1\leq i\leq N) は 1\leq A_i \leq N をみたします。
高橋君と青木君が N 回ゲームを行います。i=1,2,\ldots,N 回目のゲームは次のようにして行われます。
- 青木君が正整数 K_i を指定する。
- 青木君の指定した K_i を聞いた後、高橋君は 1 以上 N 以下の整数 S_i を選び、黒板に書く。
-
その後、 K_i 回次の操作を繰り返す。
- 黒板に x が書かれているとき、それを消し、A_x を新しく書く。
K_i 回の操作の後で黒板に書かれている整数が i ならば i 回目のゲームは高橋君の勝ち、そうでないならば青木君の勝ちとなります。
ここで、K_i,S_i は i=1,2,\ldots,N に対して独立に選ぶ事ができます。
両者が、自身が勝つために最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
両者が最善の行動をとったとき、N 回のゲームのうち高橋君が勝つ回数を出力せよ。
入力例 1
3 2 2 3
出力例 1
2
1 回目のゲームにおいて、青木君が K_1=2 を指定したとき、高橋君は S_1 として、1,2,3 のいずれを選んでも勝つことはできません。
例えば、高橋君が最初に黒板に S_1=1 と書いたとすると、2 回の操作で黒板に書かれている数は順に 1\to 2(=A_1) 、2\to 2(=A_2) と変化し、
最終的に黒板に書かれている数は 2(\neq 1) であるため、青木君の勝ちとなります。
一方、2,3 回目のゲームにおいては、青木君の指定した K_i の値によらず、高橋君はそれぞれ 2,3 を最初に黒板に書くことで勝つ事ができます。
よって、両者が、自分が勝つために最善の行動をとったとき、高橋君が勝つゲームは 2,3 回目の 2 回であるため、2 を出力します。
入力例 2
2 2 1
出力例 2
2
1 回目のゲームにおいて、高橋君は、青木君が指定した K_1 が奇数のときは 2、偶数のときは 1 を最初に黒板に書く事で勝つ事ができます。
同様に 2 回目のゲームにおいても勝つ方法が存在するため、1,2 回目のゲームのいずれでも高橋君は勝利する事ができ、2 が答えとなります。
Score : 500 points
Problem Statement
You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.
Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.
- Aoki specifies a positive integer K_i.
- After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.
-
Repeat the following K_i times.
- Replace the integer x written on the blackboard with A_x.
If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.
Find the number of rounds Takahashi wins if both players play optimally to win.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Find the number of rounds Takahashi wins if both players play optimally to win.
Sample Input 1
3 2 2 3
Sample Output 1
2
In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.
For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.
On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.
Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.
Sample Input 2
2 2 1
Sample Output 2
2
In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.
Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.