← 返回题目列表

AtCoder · abc296_e

H. 过渡游戏

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

分数: 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, i第一场比赛将按如下方式进行。

  1. 青木指定一个正整数 K_i.
  2. 知道后 K_i 青木已指定,高桥选择一个整数 S_i 之间 1 和 N,包含在内,并将其写在黑板上。
  3. 重复以下操作 K_i 次。

    • 替换整数 x 黑板上写着 黑板上写着 A_x.

If i 后写在黑板上 K_i 迭代,高桥获胜 i第轮;否则,青木获胜。
在这里, K_i 和 S_i 可以为每个独立选择 i=1,2,\ldots,N.

如果两名玩家都以最佳方式获胜,求高桥获胜的回合数。

约束

  • 1\leq N\leq 2\times 10^5
  • 1\leq A_i\leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

如果两名玩家都以最佳方式获胜,求高桥获胜的回合数。


示例输入 1

3
2 2 3

示例输出 1

2

在第一轮中,如果青木指定 K_1=2,高桥无论选择哪个选项都无法获胜 S_1: 1, 2,或 3.

例如,如果高桥写 S_1=1 在初始黑板上,这两个操作将改变这个数字如下: 1\to 2(=A_1), 2\to 2(=A_2)。黑板上的最终数字是 2(\neq 1),所以青木获胜。

另一方面,在第二轮和第三轮中,高桥可以通过写来获胜 2 和 3,分别在初始黑板上,青木指定的任何值 K_i.

因此,如果两名玩家都以最佳状态获胜,则 Takashi 赢得两轮:第二轮和第三轮。因此,您应该打印 2.


示例输入 2

2
2 1

示例输出 2

2

第一轮,高桥写字即可获胜 2 在初始黑板上如果 Aoki指定的 K_1 是奇数,并且 1 如果是偶数。

同样,高桥也有办法赢得第二轮。因此,高桥可以赢得两轮比赛:答案是 2.