Transition Game

题目描述

你得到一个长度为 $N$ 的数列：$A=(A_1,A_2,\ldots,A_N)$。这里，每个 $A_i$ $(1\leq i\leq N)$ 满足 $1\leq A_i \leq N$。 Takahashi 和 Aoki 将进行 $N$ 轮游戏。对于每个 $i=1,2,\ldots,N$，第 $i$ 轮游戏按如下方式进行。

Aoki 指定一个正整数 $K_i$。 在知道 Aoki 指定的 $K_i$ 之后，Takahashi 在 $1$ 到 $N$（含）之间选择一个整数 $S_i$，并将其写在黑板上。

重复以下操作 $K_i$ 次。

将黑板上写的整数 $x$ 替换为 $A_x$。

如果经过 $K_i$ 次迭代后黑板上写着 $i$，则 Takahashi 赢得第 $i$ 轮；否则，Aoki 赢得。
这里，對於每個 $i=1,2,\ldots,N$，$K_i$ 和 $S_i$ 可以独立选择。 如果双方都以赢为目标并且最优决策，求 Takahashi 赢得的轮数。

输入格式

从标准输入读取输入，格式如下： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

如果双方都以赢为目标并且最优决策，求 Takahashi 赢得的轮数。

3
2 2 3

2

2
2 1

2

提示

$1\leq N\leq 2\times 10^5$ $1\leq A_i\leq N$ 输入中的所有数值都是整数。在第一轮中，如果 Aoki 指定 $K_1=2$，无论 Takahashi 在 $S_1$ 选择 $1$、$2$ 还是 $3$ 都无法获胜。 例如，如果 Takahashi 在初始黑板上写 $S_1=1$，两次操作会将该数依次变为：$1\to 2(=A_1)$，$2\to 2(=A_2)$。黑板上的最终数为 $2(\neq 1)$，因此 Aoki 获胜。 另一方面，在第二和第三轮中，Takahashi 可以分别通过在初始黑板上写 $2$ 和 $3$ 获胜，无论 Aoki 指定的 $K_i$ 为何。 因此，如果双方都以赢为目标并最优决策，Takahashi 赢得两轮：第二轮和第三轮。故应输出 $2$.
在第一轮，如果 Aoki 指定的 $K_1$ 为奇数，Takahashi 可以通过在初始黑板上写 $2$ 获胜；如果为偶数，则写 $1$ 获胜。 类似地，第二轮也存在 Takahashi 获胜的方法。因此，Takahashi 可以赢得两轮：答案是 $2$.

标签: AtCoder|abc296E

来源

AtCoder|abc296E