103774: [Atcoder]ABC377 E - Permute K times 2
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：19
Solved：0
Description
Score : $475$ points
Problem Statement
You are given a permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$.
The following operation will be performed $K$ times:
- For $i=1,2,\ldots,N$, simultaneously update $P_i$ to $P_{P_i}$.
Print $P$ after all operations.
Constraints
- $1\leq N\leq2\times10^5$
- $1\leq K\leq10^{18}$
- $1\leq P_i\leq N\ (1\leq i\leq N)$
- $P_i\neq P_j\ (1\leq i\lt j\leq N)$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $K$ $P_1$ $P_2$ $\ldots$ $P_N$
Output
For the $P$ after all operations, print $P_1,P_2,\ldots,P_N$ in this order, separated by spaces.
Sample Input 1
6 3 5 6 3 1 2 4
Sample Output 1
6 1 3 2 4 5
With each operation, $P$ changes as follows:
- After the first operation, $P$ is $(2,4,3,5,6,1)$.
- After the second operation, $P$ is $(4,5,3,6,1,2)$.
- After the third operation, $P$ is $(6,1,3,2,4,5)$.
Thus, print 6 1 3 2 4 5.
Sample Input 2
5 1000000000000000000 1 2 3 4 5
Sample Output 2
1 2 3 4 5
Since $P_i=i$, $P$ does not change no matter how many operations are performed.
Sample Input 3
29 51912426 7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16
Sample Output 3
18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20
Output
得分：475分
问题陈述
给定一个排列$P=(P_1,P_2,\ldots,P_N)$，其由$(1,2,\ldots,N)$组成。
以下操作将执行$K$次：
- 对于$i=1,2,\ldots,N$，同时将$P_i$更新为$P_{P_i}$。
打印所有操作后的$P$。
约束条件
- $1\leq N\leq2\times10^5$
- $1\leq K\leq10^{18}$
- $1\leq P_i\leq N\ (1\leq i\leq N)$
- $P_i\neq P_j\ (1\leq i\lt j\leq N)$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出：
$N$ $K$ $P_1$ $P_2$ $\ldots$ $P_N$
输出
对于所有操作后的$P$，按顺序打印$P_1,P_2,\ldots,P_N$，用空格分隔。
示例输入1
6 3 5 6 3 1 2 4
示例输出1
6 1 3 2 4 5
每次操作后，$P$的变化如下：
- 第一次操作后，$P$为$(2,4,3,5,6,1)$。
- 第二次操作后，$P$为$(4,5,3,6,1,2)$。
- 第三次操作后，$P$为$(6,1,3,2,4,5)$。
因此，打印6 1 3 2 4 5。
示例输入2
5 1000000000000000000 1 2 3 4 5
示例输出2
1 2 3 4 5
由于$P_i=i$，无论执行多少次操作，$P$都不会改变。
示例输入3
29 51912426 7 24 8 23 6 1 4 19 11 18 20 9 17 28 22 27 15 2 12 26 10 13 14 25 5 29 3 21 16
示例输出3
18 23 16 24 21 10 2 27 19 7 12 8 13 5 15 26 17 4 3 9 1 22 25 14 28 11 29 6 20