Permutation Shift
题意翻译
### 题目描述
一个长度为 $n$ 的初始排列为 $[1,2,3,4,\ldots,n]$ 。
对其进行下列操作:
* 首先,我们将其循环移动 $k$ 位, $k$ 为一个未知数 $(0 \leq k \leq n-1)$ 。
将一个长度为 $n$ 的数组循环移动k位就是将原数组最后 $k$ 位移动到第 $1 \sim k$ 位,并将其余 $n-k$ 位移动到第 $k+1 \sim n$ 位。比如说,我们将 $[1,2,3,4,5,6]$ 循环移动两位,就是 $[5,6,1,2,3,4]$ 。
* 然后,我们将数组中任意两个数交换,最多进行 $m$ 次。
给定 $n,m$ 和最后的结果,你需要找出所有可能的 $k$ 值。
### 输入格式
第一行为一个整数 $t$ 代表测试数据个数($1 \leq t \leq 10^5$)。
每个测试数据分为两行:
第一行为 $n,m$($3 \leq n \leq 3 \times 10^5,0 \leq m \leq \dfrac{n}{3}$)。
第二行有 $n$ 个整数 $p_1,p_2,\ldots,p_n$($1 \leq p_i \leq n$ ,每个 $1 \sim n$ 的整数均只出现一次)。
所有测试数据的 $n$ 之和不超过 $3 \times 10^5$。
### 输出格式
对于每一个测试数据:
首先输出一个正整数 $r$ 代表可能的 $k$ 的个数。
接下来,输出 $r$ 个整数 $k_1,k_2,\ldots,k_r$($0 \leq k_i \leq n-1$)代表所有的 $k$ 值,按升序排列。
题目描述
An identity permutation of length $ n $ is an array $ [1, 2, 3, \dots, n] $ .
We performed the following operations to an identity permutation of length $ n $ :
- firstly, we cyclically shifted it to the right by $ k $ positions, where $ k $ is unknown to you (the only thing you know is that $ 0 \le k \le n - 1 $ ). When an array is cyclically shifted to the right by $ k $ positions, the resulting array is formed by taking $ k $ last elements of the original array (without changing their relative order), and then appending $ n - k $ first elements to the right of them (without changing relative order of the first $ n - k $ elements as well). For example, if we cyclically shift the identity permutation of length $ 6 $ by $ 2 $ positions, we get the array $ [5, 6, 1, 2, 3, 4] $ ;
- secondly, we performed the following operation at most $ m $ times: pick any two elements of the array and swap them.
You are given the values of $ n $ and $ m $ , and the resulting array. Your task is to find all possible values of $ k $ in the cyclic shift operation.
输入输出格式
输入格式
The first line contains one integer $ t $ ( $ 1 \le t \le 10^5 $ ) — the number of test cases.
Each test case consists of two lines. The first line contains two integers $ n $ and $ m $ ( $ 3 \le n \le 3 \cdot 10^5 $ ; $ 0 \le m \le \frac{n}{3} $ ).
The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ , each integer from $ 1 $ to $ n $ appears in this sequence exactly once) — the resulting array.
The sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .
输出格式
For each test case, print the answer in the following way:
- firstly, print one integer $ r $ ( $ 0 \le r \le n $ ) — the number of possible values of $ k $ for the cyclic shift operation;
- secondly, print $ r $ integers $ k_1, k_2, \dots, k_r $ ( $ 0 \le k_i \le n - 1 $ ) — all possible values of $ k $ in increasing order.
输入输出样例
输入样例 #1
4
4 1
2 3 1 4
3 1
1 2 3
3 1
3 2 1
6 0
1 2 3 4 6 5
输出样例 #1
1 3
1 0
3 0 1 2
0
说明
Consider the example:
- in the first test case, the only possible value for the cyclic shift is $ 3 $ . If we shift $ [1, 2, 3, 4] $ by $ 3 $ positions, we get $ [2, 3, 4, 1] $ . Then we can swap the $ 3 $ -rd and the $ 4 $ -th elements to get the array $ [2, 3, 1, 4] $ ;
- in the second test case, the only possible value for the cyclic shift is $ 0 $ . If we shift $ [1, 2, 3] $ by $ 0 $ positions, we get $ [1, 2, 3] $ . Then we don't change the array at all (we stated that we made at most $ 1 $ swap), so the resulting array stays $ [1, 2, 3] $ ;
- in the third test case, all values from $ 0 $ to $ 2 $ are possible for the cyclic shift:
- if we shift $ [1, 2, 3] $ by $ 0 $ positions, we get $ [1, 2, 3] $ . Then we can swap the $ 1 $ -st and the $ 3 $ -rd elements to get $ [3, 2, 1] $ ;
- if we shift $ [1, 2, 3] $ by $ 1 $ position, we get $ [3, 1, 2] $ . Then we can swap the $ 2 $ -nd and the $ 3 $ -rd elements to get $ [3, 2, 1] $ ;
- if we shift $ [1, 2, 3] $ by $ 2 $ positions, we get $ [2, 3, 1] $ . Then we can swap the $ 1 $ -st and the $ 2 $ -nd elements to get $ [3, 2, 1] $ ;
- in the fourth test case, we stated that we didn't do any swaps after the cyclic shift, but no value of cyclic shift could produce the array $ [1, 2, 3, 4, 6, 5] $ .