【NOIP模拟赛】滑板鞋

2014年10月18日1,9510

题目背景

我的滑板鞋时尚时尚最时尚
回家的路上我情不自禁
摩擦 摩擦
在这光滑的地上摩擦
月光下我看到自己的身影有时很远有时很近
感到一种力量驱使我的脚步
有了滑板鞋天黑都不怕

题目描述

你在魅力之都购买了一双时尚的滑板鞋,你非常兴奋地到处摩擦!

hzwer很想问一个问题:按照你的行动方式,你从某个结点摩擦(移动)K步后能到的目的地

这显然是一个很简单的问题,但是蒟蒻hzwer总是问个不停,所以你决定写一个程序回答他的询问

输入格式

第一行两个数n,m表示结点个数和询问次数

接下来n行,第i个数一个数a[i]表示你在第i个结点的话,下一步会移动到第a[i]个结点

接下来m行,每行两个数t,k,蒟蒻hzwer询问如果你当前在第t个结点,k步之后你会到第几个节点

输出格式

m行为每次询问的结果

样例数据 1

输入

3 2
2
3
2
1 2
2 4

输出

3
2

备注

共十个测试点,每个测试点数据规模如下所示

1.n=10^2,m=n,k<=10^2

2.n=10^3,m=n,k<=10^3

3.n=10^4,m=1,k<=10^9

4.n=10^5,m=1,k<=10^9

5.n=10^5,m=1,k<=10^12

6.n=10^5,m=1,k<=10^15

7.n=10^5,m=1,k<=10^18

8.n=10^5,m=n,k<=10^12

9.n=10^5,m=n,k<=10^15

10.n=10^5,m=n,k<=10^18

题解

第一种做法直接暴力找循环节。。。

可以得70分

正解裸倍增

f[k,i]代表从i开始走2^k步会到哪里,初始f[0,i]=next[i]

f[k,i]=f[k-1,f[k-1,i]],复杂度m*log(n)

本题来自orz模拟赛

暴力

正解