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] $ .