Inverse Transformation

题意翻译

### 题目描述 一位科学家正在研究一个自我生长的长度为 $n$ 的排列 $a_1,a_2,\ldots,a_n$。 排列每天都会变化，每一天，元素 $x$ 都会变成 $a_x$，即 $a_x$ 会变成 $a_{a_x}$。具体地： - 第一天，排列会变成 $b$，其中 $b_x = a_{a_x}$； - 第二天，排列会变成 $c$，其中 $c_x = b_{b_x}$； - $\ldots$ 例如，若 $a = [2,3,1]$，则第一天会变成 $[3,1,2]$，第二天会变成 $[2,3,1]$。 定义 $\sigma(x) = a_x$，定义 $f(x)$ 为最小的正整数 $m$ 满足 $\sigma^m(x) = x$，其中 $\sigma^m(x) = \underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ 个 } \sigma}(x) \ldots))$。 例如，$a = [2,3,1]$ 时，$\sigma(1) = 2$，$\sigma^2(1) = \sigma(\sigma(1)) = \sigma(2) = 3$，$\sigma^3(1) = \sigma(\sigma(\sigma(1))) = \sigma(3) = 1$，故 $f(1) = 3$。再例如 $a = [4,2,1,3]$，$\sigma(2) = 2$ 故 $f(2) = 1$；$\sigma(3) = 1$，$\sigma^2(3) = 4$，$\sigma^3(3) = 3$ 故 $f(3) = 3$。 现在给出第 $k$ 天的排列 $a'$。求找出一个初始的排列 $a$ 使得 $\sum\limits^n_{i=1} \dfrac{1}{f(i)}$ 最小。 ~~因为鬼畜的 sigma 和审核争了好久~~ ### 输入格式 第一行一个正整数 $t$（$1\le t\le 10^4$）表示数据组数。 每组测试数据第一行两个正整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^9$），含义见题目描述。 第二行 $n$ 个正整数 $a'_1,a'_2,\ldots,a'_n$（$1 \le a'_i \le n$）表示第 $n$ 天的排列。 保证所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 输出格式 对于每组测试数据，若不存在这样的初始排列 $a$ 输出 `NO`。若存在输出 `YES`，并在下一行输出 $\sum\limits^n_{i=1} \dfrac{1}{f(i)}$ 最小的一个排列，若有多个，输出任意一个即可。 ### 样例解释 第二组测试数据中，初始排列可以是 $a = [6,2,5,7,1,3,4]$，它第一天会变成 $[3,2,1,4,6,5,7]$，第二天（即第 $k$ 天）会变成 $a' = [1,2,3,4,5,6,7]$。同时，所有符合这个条件的 $a$ 中，它的 $\sum\limits^n_{i=1} \dfrac{1}{f(i)}$ 最小，是 $\dfrac{1}{4}+\dfrac{1}{1}+\dfrac{1}{4}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{2}=3$。 第五组测试数据中，初始排列可能是 $a = [4,2,1,3]$，它第一天会变成 $[3,2,4,1]$，第二天变会 $[4,2,1,3]$，如此循环。所以，第八天（第 $k$ 天）它会变成 $a' = [4,2,1,3]$。同时它的 $\sum\limits^n_{i=1} \dfrac{1}{f(i)} = \dfrac{1}{3} + \dfrac{1}{1} + \dfrac{1}{3} + \dfrac{1}{3} = 2$ 最小。

题目描述

A permutation scientist is studying a self-transforming permutation $ a $ consisting of $ n $ elements $ a_1,a_2,\ldots,a_n $ . A permutation is a sequence of integers from $ 1 $ to $ n $ of length $ n $ containing each number exactly once. For example, $ [1] $ , $ [4, 3, 5, 1, 2] $ are permutations, while $ [1, 1] $ , $ [4, 3, 1] $ are not. The permutation transforms day by day. On each day, each element $ x $ becomes $ a_x $ , that is, $ a_x $ becomes $ a_{a_x} $ . Specifically: - on the first day, the permutation becomes $ b $ , where $ b_x = a_{a_x} $ ; - on the second day, the permutation becomes $ c $ , where $ c_x = b_{b_x} $ ; - $ \ldots $ For example, consider permutation $ a = [2,3,1] $ . On the first day, it becomes $ [3,1,2] $ . On the second day, it becomes $ [2,3,1] $ .You're given the permutation $ a' $ on the $ k $ -th day. Define $ \sigma(x) = a_x $ , and define $ f(x) $ as the minimal positive integer $ m $ such that $ \sigma^m(x) = x $ , where $ \sigma^m(x) $ denotes $ \underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ times}}(x) \ldots)) $ . For example, if $ a = [2,3,1] $ , then $ \sigma(1) = 2 $ , $ \sigma^2(1) = \sigma(\sigma(1)) = \sigma(2) = 3 $ , $ \sigma^3(1) = \sigma(\sigma(\sigma(1))) = \sigma(3) = 1 $ , so $ f(1) = 3 $ . And if $ a=[4,2,1,3] $ , $ \sigma(2) = 2 $ so $ f(2) = 1 $ ; $ \sigma(3) = 1 $ , $ \sigma^2(3) = 4 $ , $ \sigma^3(3) = 3 $ so $ f(3) = 3 $ . Find the initial permutation $ a $ such that $ \sum\limits^n_{i=1} \dfrac{1}{f(i)} $ is minimum possible.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le k \le 10^9 $ ) — the length of $ a $ , and the last day. The second line contains $ n $ integers $ a'_1,a'_2,\ldots,a'_n $ ( $ 1 \le a'_i \le n $ ) — the permutation on the $ k $ -th day. It's guaranteed that the sum of $ n $ does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, if at least one initial $ a $ consistent with the given $ a' $ exists, print "YES", then print $ n $ integers $ a_1,a_2,\ldots,a_n $ — the initial permutation with the smallest sum $ \sum\limits^n_{i=1} \dfrac{1}{f(i)} $ . If there are multiple answers with the smallest sum, print any. If there are no valid permutations, print "NO".

输入输出样例

输入样例 #1

10
5 3
1 2 3 4 5
7 2
1 2 3 4 5 6 7
8 998
1 2 3 4 5 6 7 8
6 1
6 3 5 4 1 2
4 8
4 2 1 3
9 1
1 5 4 8 7 6 3 2 9
5 9999999
2 3 4 5 1
7 97843220
4 6 1 2 7 5 3
3 1000000000
2 1 3
12 3
8 9 10 1 5 3 11 4 7 6 12 2

输出样例 #1

YES
2 3 4 1 5
YES
6 2 5 7 1 3 4
YES
2 3 4 5 6 7 8 1
YES
3 1 6 4 2 5
YES
4 2 1 3
NO
YES
3 4 5 1 2
YES
2 5 4 6 3 7 1
NO
YES
3 7 8 6 5 1 12 10 11 4 2 9

说明

In the second test case, the initial permutation can be $ a = [6,2,5,7,1,3,4] $ , which becomes $ [3,2,1,4,6,5,7] $ on the first day and $ a' = [1,2,3,4,5,6,7] $ on the second day (the $ k $ -th day). Also, among all the permutations satisfying that, it has the minimum $ \sum\limits^n_{i=1} \dfrac{1}{f(i)} $ , which is $ \dfrac{1}{4}+\dfrac{1}{1}+\dfrac{1}{4}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{2}=3 $ . In the fifth test case, the initial permutation can be $ a = [4,2,1,3] $ , which becomes $ [3,2,4,1] $ on the first day, $ [4,2,1,3] $ on the second day, and so on. So it finally becomes $ a' = [4,2,1,3] $ on the $ 8 $ -th day (the $ k $ -th day). And it has the minimum $ \sum\limits^n_{i=1} \dfrac{1}{f(i)} = \dfrac{1}{3} + \dfrac{1}{1} + \dfrac{1}{3} + \dfrac{1}{3} = 2 $ .

**题目大意：**

一个科学家正在研究一个长度为 $ n $ 的自我生长排列 $ a_1, a_2, \ldots, a_n $。排列每天都会变化，具体地，每一天，元素 $ x $ 都会变成 $ a_x $，即 $ a_x $ 会变成 $ a_{a_x} $。给定第 $ k $ 天的排列 $ a' $，要求找出一个初始的排列 $ a $ 使得 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小，其中 $ f(x) $ 是最小的正整数 $ m $ 满足 $ \sigma^m(x) = x $，而 $ \sigma(x) = a_x $ 且 $ \sigma^m(x) $ 表示 $ \sigma $ 函数对 $ x $ 连续作用 $ m $ 次的结果。

**输入输出数据格式：**

**输入格式：**
- 第一行一个正整数 $ t $（$ 1 \le t \le 10^4 $）表示数据组数。
- 每组测试数据第一行两个正整数 $ n $ 和 $ k $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le k \le 10^9 $）。
- 第二行 $ n $ 个正整数 $ a'_1, a'_2, \ldots, a'_n $（$ 1 \le a'_i \le n $）表示第 $ k $ 天的排列。

**输出格式：**
- 对于每组测试数据，若不存在这样的初始排列 $ a $ 输出 `NO`。若存在输出 `YES`，并在下一行输出 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小的一个排列，若有多个，输出任意一个即可。

**样例解释：**

第二组测试数据中，初始排列可以是 $ a = [6,2,5,7,1,3,4] $，它第一天会变成 $ [3,2,1,4,6,5,7] $，第二天（即第 $ k $ 天）会变成 $ a' = [1,2,3,4,5,6,7] $。同时，所有符合这个条件的 $ a $ 中，它的 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小，是 $ \frac{1}{4} + \frac{1}{1} + \frac{1}{4} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{2} = 3 $。

第五组测试数据中，初始排列可能是 $ a = [4,2,1,3] $，它第一天会变成 $ [3,2,4,1] $，第二天变会 $ [4,2,1,3] $，如此循环。所以，第八天（第 $ k $ 天）它会变成 $ a' = [4,2,1,3] $。同时它的 $ \sum_{i=1}^{n} \frac{1}{f(i)} = \frac{1}{3} + \frac{1}{1} + \frac{1}{3} + \frac{1}{3} = 2 $ 最小。**题目大意：** 一个科学家正在研究一个长度为 $ n $ 的自我生长排列 $ a_1, a_2, \ldots, a_n $。排列每天都会变化，具体地，每一天，元素 $ x $ 都会变成 $ a_x $，即 $ a_x $ 会变成 $ a_{a_x} $。给定第 $ k $ 天的排列 $ a' $，要求找出一个初始的排列 $ a $ 使得 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小，其中 $ f(x) $ 是最小的正整数 $ m $ 满足 $ \sigma^m(x) = x $，而 $ \sigma(x) = a_x $ 且 $ \sigma^m(x) $ 表示 $ \sigma $ 函数对 $ x $ 连续作用 $ m $ 次的结果。 **输入输出数据格式：** **输入格式：** - 第一行一个正整数 $ t $（$ 1 \le t \le 10^4 $）表示数据组数。 - 每组测试数据第一行两个正整数 $ n $ 和 $ k $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le k \le 10^9 $）。 - 第二行 $ n $ 个正整数 $ a'_1, a'_2, \ldots, a'_n $（$ 1 \le a'_i \le n $）表示第 $ k $ 天的排列。 **输出格式：** - 对于每组测试数据，若不存在这样的初始排列 $ a $ 输出 `NO`。若存在输出 `YES`，并在下一行输出 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小的一个排列，若有多个，输出任意一个即可。 **样例解释：** 第二组测试数据中，初始排列可以是 $ a = [6,2,5,7,1,3,4] $，它第一天会变成 $ [3,2,1,4,6,5,7] $，第二天（即第 $ k $ 天）会变成 $ a' = [1,2,3,4,5,6,7] $。同时，所有符合这个条件的 $ a $ 中，它的 $ \sum_{i=1}^{n} \frac{1}{f(i)} $ 最小，是 $ \frac{1}{4} + \frac{1}{1} + \frac{1}{4} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{2} = 3 $。 第五组测试数据中，初始排列可能是 $ a = [4,2,1,3] $，它第一天会变成 $ [3,2,4,1] $，第二天变会 $ [4,2,1,3] $，如此循环。所以，第八天（第 $ k $ 天）它会变成 $ a' = [4,2,1,3] $。同时它的 $ \sum_{i=1}^{n} \frac{1}{f(i)} = \frac{1}{3} + \frac{1}{1} + \frac{1}{3} + \frac{1}{3} = 2 $ 最小。