CF1218H Function Composition

我们绝对不会再用那些千篇一律的故事来打扰你，比如 Alice 发现了一个数组，或者 Alice 和 Bob 玩某个无聊的游戏。这一次，你将直接得到一段简单明了的文本。 首先，我们定义一些内容。我们在数组 $A$ 上定义函数 $F$，使得 $F(i, 1) = A[i]$，并且当 $m > 1$ 时，$F(i, m) = A[F(i, m - 1)]$。换句话说，$F(i, m)$ 表示将 $A$ 复合应用 $m$ 次后的结果，即 $A[...A[i]]$，共应用 $m$ 次。 给定一个长度为 $N$ 的非负整数数组。你需要回答 $Q$ 个询问。每个询问包含两个数字 $m$ 和 $y$。对于每个询问，求有多少个 $x$ 满足 $F(x, m) = y$。

第一行包含一个整数 $N$，表示数组 $A$ 的长度，$1 \leq N \leq 2 \cdot 10^5$。 第二行包含 $N$ 个非负整数，表示数组 $A$，其中 $1 \leq A_i \leq N$。 第三行包含一个整数 $Q$，表示询问的数量，$1 \leq Q \leq 10^5$。 接下来的 $Q$ 行，每行包含两个整数 $m$ 和 $y$，$1 \leq m \leq 10^{18}$，$1 \leq y \leq N$。

输出恰好 $Q$ 行，每行一个整数，表示对应询问的答案。答案需按照询问的顺序输出。

对于第一个询问，可以注意到 $F(3, 10) = 1$，$F(9, 10) = 1$，$F(10, 10) = 1$。 对于第二个询问，没有 $x$ 满足 $F(x, 5) = 7$。 对于第三个询问，$F(5, 10) = 6$ 成立。 对于第四个询问，$F(3, 1) = 1$。 对于第五个询问，没有 $x$ 满足 $F(x, 10) = 8$。 由 ChatGPT 4.1 翻译