TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

94.7% (143/151)

Submission's AC Ratio

59.3% (210/354)

Tags

Description

蛋餅是個熱愛函數的建中學生,無論是多項式函數、三角函數、指對數函數,蛋餅都研究得十分透徹。而今天,他發現了一個十分有趣的函數,決定好好研究一番。

這個函數十分的特別,他的輸入只能是一個介於$1$到$N$之間的正整數,而他的輸出也會是一個介於$1$到$N$之間的正整數。更特別的是,任意兩個不一樣的數字代入函數當中,得到的輸出都不相同。

蛋餅最喜歡對函數做一件事,他把這件事稱作「函數的迭代」。具體來說,就是把剛從函數得到的值,再代入函數。一個數對某個函數的「$k$次迭代」就是指將一個數連續代入函數$k$次,所得到的值。舉例來說,蛋餅有個數字叫做$x$,那麼$x$的零次迭代就是$x$,$x$的一次迭代就是$f(x)$,$x$的二次迭代就是$f(f(x))$或記作$f^ 2(x)$,$x$的三次迭代就是$f(f(f(x)))$或記作$f^ 3(x)$…以此類推。

蛋餅覺得如果要分析如此複雜的函數,會需要程式的幫助。因此,他想請你幫忙解決以下的問題。蛋餅告訴了你將$1$到$N$依序代入這個函數後所得到的結果,而接下來蛋餅會詢問$Q$次,每次詢問兩個整數$a,b$。你必須回答他,$a$對這個函數迭代$b$次,也就是$f^ b(a)$是多少。

Input Format

輸入的第一行為一個正整數$N$,意義如題目所敘。
接下來一行有$N$個整數,分別代表$f(1),f(2),...,f(N)$。
接下來一行有一個正整數$Q$,表示詢問的次數。
接下來共$Q$行,其中第$i$行有兩個整數$a_i,b_i$,分別表示詢問的$a$與$b$。

對於所有測試資料,保證$N\leq 10^ 5$,$Q\leq 800$,$1\leq a_i\leq N$,$0\leq b_i<N$。

Output Format

輸出共$Q$行,每一行代表一筆詢問的答案。

Sample Input 1

4
2 4 1 3
2
3 2
4 1

Sample Output 1

2
3

Hints

對於範例測資,第一筆詢問$f^ 2(3)$,也就是$f(f(3))=f(1)=2$,所以輸出$2$。第二筆詢問$f^ 1(4)=f(4)=3$,所以輸出$3$。

Problem Source

110學年度建國中學校內資訊能力競賽初試pA

Subtasks

No. Testdata Range Constraints Score
1 0~11 $N \le 100, Q \le 40$ 70
2 0~28 無額外限制 30

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1 2
1 1000 131072 65536 1 2
2 1000 131072 65536 1 2
3 1000 131072 65536 1 2
4 1000 131072 65536 1 2
5 1000 131072 65536 1 2
6 1000 131072 65536 1 2
7 1000 131072 65536 1 2
8 1000 131072 65536 1 2
9 1000 131072 65536 1 2
10 1000 131072 65536 1 2
11 1000 131072 65536 1 2
12 1000 131072 65536 2
13 1000 131072 65536 2
14 1000 131072 65536 2
15 1000 131072 65536 2
16 1000 131072 65536 2
17 1000 131072 65536 2
18 1000 131072 65536 2
19 1000 131072 65536 2
20 1000 131072 65536 2
21 1500 131072 65536 2
22 1500 131072 65536 2
23 1500 131072 65536 2
24 1500 131072 65536 2
25 1500 131072 65536 2
26 1500 131072 65536 2
27 1500 131072 65536 2
28 1500 131072 65536 2