AT_abc296_e [ABC296E] Transition Game

题目描述

给定一个长度为 $N$ 的数列 $A=(A_1,A_2,\ldots,A_N)$。其中，每个 $A_i$（$1\leq i\leq N$）满足 $1\leq A_i\leq N$。

高桥君和青木君要进行 $N$ 次游戏。第 $i$ 次游戏（$i=1,2,\ldots,N$）的规则如下：

1. 青木君指定一个正整数 $K_i$。

2. 听到青木君指定的 $K_i$ 后，高桥君选择一个 $1$ 到 $N$ 之间的整数 $S_i$，并写在黑板上。

3. 接下来，重复 $K_i$ 次如下操作：

   • 如果黑板上写着 $x$，则擦掉它，并写上 $A_x$。

经过 $K_i$ 次操作后，如果黑板上写着的整数是 $i$，则高桥君获胜，否则青木君获胜。 这里，$K_i,S_i$ 可以对每个 $i=1,2,\ldots,N$ 独立选择。

当两人都采取对自己最有利的策略时，请你求出 $N$ 次游戏中高桥君能获胜的次数。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出当双方都采取最优策略时，高桥君能获胜的游戏次数。

输入输出样例 #1

输入 #1

3
2 2 3

输出 #1

2

输入输出样例 #2

输入 #2

2
2 1

输出 #2

2

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $1\leq A_i\leq N$
• 输入均为整数

样例解释 1

在第 $1$ 次游戏中，如果青木君指定 $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$ 是多少，高桥君都可以分别选择 $2,3$ 作为初始数字获胜。 因此，当双方都采取最优策略时，高桥君能获胜的游戏为第 $2,3$ 次，共 $2$ 次，所以输出 $2$。

样例解释 2

在第 $1$ 次游戏中，高桥君可以根据青木君指定的 $K_1$ 的奇偶性，若为奇数则选择 $2$，若为偶数则选择 $1$，从而获胜。同理，在第 $2$ 次游戏中也存在获胜的方法，因此第 $1,2$ 次游戏高桥君都能获胜，答案为 $2$。

由 ChatGPT 4.1 翻译