Permutation Shift (Codeforces 1553E)
Tags: Math, dsu

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.

Input: 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$$$.

Output: 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. 

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

Sample Inputs:
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

Sample Outputs:
1 3
1 0
3 0 1 2
0

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, m) = readInts()
    arr = readList()
    (cnt, pos) = ([0] * n, [0] * (n + 1))
    for i in range(n):
        cnt[(i - arr[i] + 1) % n] += 1
        pos[arr[i]] = i
    (cnt, ans) = ([n - v for v in cnt], [])
    for i in range(n):
        if cnt[i] > 2 * m:
            continue
        (tmp, pt, v) = (list(arr), list(pos), 0)
        for j in range(n):
            if tmp[(i + j) % n] == j + 1:
                continue
            k = pt[j + 1]
            (tmp[(i + j) % n], tmp[k]) = (tmp[k], tmp[(i + j) % n])
            (pt[tmp[(i + j) % n]], pt[tmp[k]]) = ((i + j) % n, k)
            v += 1
            if v > m:
                break
        if v <= m:
            ans.append(i)
    return [len(ans)] + ans
for _ in range(int(input())):
    print(*solve())

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    (n, m) = map(int, input().split())
    p = list(map(int, input().split()))
    s = [0] * n
    for i in range(n):
        v = p[i] - 1
        s[(i - v) % n] += 1
    z = n - 2 * m
    r = []
    for i in range(n):
        if s[i] >= z:
            w = [True] * n
            c = 0
            for j in range(n):
                if w[j]:
                    c += 1
                    while w[j]:
                        w[j] = False
                        v = p[j] - 1
                        j = (v + i) % n
            if n - c <= m:
                r.append(i)
    print(len(r), end=' ')
    print(' '.join(map(str, r)))
for i in range(int(input())):
    solve()

Solution (Python):
t = int(input())
results = []
for i in range(t):
    (n, m) = map(int, input().split())
    nums = [int(num) - 1 for num in input().split()]
    counts = {}
    for (j, num) in enumerate(nums):
        val = (j - num) % n
        counts[val] = counts.get(val, 0) + 1
    res = []
    for k in counts:
        if counts[k] < n - 2 * m:
            continue
        shifted = nums[k:] + nums[:k]
        tested = [True] * n
        to_swap = 0
        for index in range(len(tested)):
            current_count = 0
            current_index = index
            while True:
                if tested[current_index]:
                    tested[current_index] = False
                    current_count += 1
                    current_index = shifted[current_index]
                else:
                    break
            if current_count != 0:
                to_swap += current_count - 1
        if to_swap <= m:
            res.append(k)
    results.append(res)
for i in range(t):
    if len(results[i]) == 0:
        print(0)
    else:
        print(len(results[i]), end=' ')
        print(' '.join((str(k) for k in sorted(results[i]))))