← 返回题目列表

Codeforces · 1218/H

H. 功能构成

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

当爱丽丝发现数组或当爱丽丝和鲍勃玩一些愚蠢的游戏时,我们绝对不会用另一个通用故事来打扰您。这次您将得到一个简单的纯文本。

首先,让我们定义几件事。我们在数组 $$$A$$$ 上定义函数 $$$F$$$,使得 $$$F(i, 1) = A[i]$$$ 和 $$$F(i, m) = A[F(i, m - 1)]$$$ 对于 $$$m > 1$$$。换句话说,值 $$$F(i, m)$$$ 表示组合 $$$A[...A[i]]$$$ 应用了 $$$m$$$ 次。

给定一个长度为 $$$N$$$ 且包含非负整数的数组。您需要对 $$$Q$$$ 查询给出答案。每个查询由两个数字组成 - $$$m$$$ 和 $$$y$$$。对于每个查询,确定存在多少个 $$$x$$$ 使得 $$$F(x,m) = y$$$。

输入

第一行包含一个整数 $$$N$$$ $$$(1 \leq N \leq 2 \cdot 10^5)$$$ – 数组 $$$A$$$ 的大小。下一行包含 $$$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$$$ 行,每行有一个整数代表解决方案。按照询问的顺序输出解决方案。

示例

输入 #1

10
2 3 1 5 6 4 2 10 7 7
5
10 1
5 7
10 6
1 1
10 8

输出 #1

3
0
1
1
0

注意

对于第一个查询,我们可以注意到 $$$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$$$。