← 返回题目列表

AtCoder · abc377_e

H. 排列 K 次 2

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

分数: 475 点

问题陈述

给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

将执行以下操作 K 次:

  • 对于 i=1,2,\ldots,N, 同时 更新 P_i to 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 is (2,4,3,5,6,1).
  • 第二次操作后, P is (4,5,3,6,1,2).
  • 第三次操作后, 无论执行多少次操作, P is (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