| CCF CAT NAEC 2025 (Final) |
|---|
| Finished |
对于一个长度为 $$$n$$$ 的整数序列 $$$[a_1, a_2, a_3, \cdots, a_n]$$$,如果其中 $$$1$$$ 到 $$$n$$$ 之间的每个数刚好出现一次,那么我们称它是一个长度为 $$$n$$$ 的排列。
例如,$$$[1, 3, 2, 4]$$$、$$$[1, 6, 2, 3, 4, 5]$$$、$$$[1]$$$ 都是排列,而 $$$[1, 1, 4]$$$ 不是。
对于两个长度同样为 $$$n$$$ 的排列 $$$a$$$ 和 $$$b$$$,我们定义 $$$b$$$ 对 $$$a$$$ 的排列置换 $$$F(a, b)$$$ 为:
$$$$$$ F(a, b) = [a_{b_1}, a_{b_2}, a_{b_3}, \cdots, a_{b_n}] $$$$$$
对于长度为 $$$n$$$ 的排列 $$$a$$$ 以及非负整数 $$$x$$$,我们定义 $$$a$$$ 的 $$$x$$$ 次自身置换 $$$G(a, x)$$$ 为:
$$$$$$ G(a, x) = \begin{cases} a & \text {if } x = 0\\ F \left ( G(a, x-1), G(a, x-1) \right ) &\text{else} \end{cases} $$$$$$
给定一个长度为 $$$n$$$ 的排列 $$$a$$$ 以及非负整数 $$$x$$$,请你计算并输出 $$$a$$$ 的 $$$x$$$ 次自身置换 $$$G(a, x)$$$。
第一行包含一个整数 $$$n$$$($$$1 \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, a_3, \cdots, a_n$$$,用空格分隔,表示排列 $$$a$$$。
第三行包含一个整数 $$$x$$$($$$0 \leq x \leq 10^{10^5}$$$)。
输出一行,包含 $$$n$$$ 个整数,用空格分隔,表示计算结果。
52 3 1 5 43
3 1 2 4 5
129 7 8 1 2 3 12 6 11 5 4 101145141919810
1 5 8 4 10 3 2 6 9 12 11 7
| Name |
|---|


