徐老师的银白森林
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
在不知名的银白森林，共有 $n$ 个节点。每个节点处，生活着一名魔法师。在每个节点，有一条通向其他节点的单向道路。
这天，徐老师被一阵神秘的力量所影响，落在了某个节点上，并且接下来徐老师会沿着单向道路移动 $k$ 次。
每利用单向道路移动到一个节点时，这个节点处的魔法师会为徐老师进行一次赐福，获得等于节点编号数量的祝福之力。（例如，当节点编号为 $3$ 时，经过这个节点可以获得 $3$ 点祝福之力）
注意，当重复经过某个节点时，魔法师是会多次为徐老师进行赐福的。
而现在你提前掌握了整个银白森林的道路图，而徐老师有可能被传送到某个节点 $x$，并且他将会移动 $k$ 步
你可以提前预测一下徐老师会获得多少点祝福之力吗？
这样你就可以通过感应对应祝福之力的拥有者，将徐老师救回来了！
输入格式
输入第一行包含两个整数 $n$ 和 $q$，表示银白森林有 $n$ 个节点，以及 $q$ 次询问接下来一行包含 $n$ 个整数，第 $i$ 个数字 $a_i$ 表示节点 $i$ 的单向道路通向 $a_i$，允许 $a_i = i$
接下来 $q$ 行
每行包含两个整数 $x,k$ 表示一次询问，询问当徐老师被传送到 $x$ 节点并且移动 $k$ 次后会获得多少祝福之力
|测试数据|$n,q$|$k$|特殊性质|
|:---:|:---:|:---:|:---:|
|$1 \sim 2$|$1 \leq n,q \leq 10$|$1 \leq k \leq 100$|无|
|$3 \sim 4$|$1 \leq n,q \leq 100000$|$1 \leq k \leq 10^{12}$|$a_i=i+1$且$a_n=1$|
|$5 \sim 10$|$1 \leq n,q \leq 100000$|$1 \leq k \leq 10^{12}$|无|
输出格式
对于每组询问输出徐老师会获得的祝福之力数量样例
6 2
2 3 1 5 6 6
1 5
4 511
29提示
第一次询问是从 $1$ 出发移动 $5$ 次，路径为 $1 -> 2 -> 3 -> 1 -> 2 ->3$获得的祝福之力为 $2+3+1+2+3=12$
第二次询问是从 $4$ 出发移动 $5$ 次，路径为 $4 -> 5 -> 6 -> 6 -> 6 ->6$
获得的祝福之力为 $5+6+6+6+6=29$
23CSP-S秋季提高组模拟赛(5)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-1 17:30
- 结束于
- 2023-10-11 17:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 23
