链接：https://codeforces.com/problemset/problem/1553/E

这道题先破例先上一波代码

#include <bits/stdc++.h>
using namespace std;
int n,m,p[355000];
bool check(int index){
	vector<int>v;
	v.push_back(0);
	for(int i=index+1;i<=n;i++) v.push_back(p[i]);
	for(int i=1;i<=index;i++) v.push_back(p[i]);
	int tot=0;
	map<int,int>nxt;
	map<int,bool>used;
	for(int i=1;i<=n;i++){
		nxt[i]=v[i];
	}
	for(int i=1;i<=n;i++){
		if(used[i]) continue;
		tot++;
		int now=nxt[i];
		while(!used[now]){
			used[now]=1;now=nxt[now];
		}
	}
	return n-tot<=m;
}
void solve(){
	map<int,int>cnt;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		cnt[(i-p[i]+n)%n]++;
	}
	vector<int>ans;
	for(int i=0;i<n;i++){
		if(n-2*m<=cnt[i]&&check(i)) ans.push_back(i);
	}
	cout<<ans.size();
	for(auto i:ans) cout<<" "<<i;
	cout<<endl;
}
int main(){
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

诶，看着很像n²复杂度对不对。实则它只是一个n的复杂度，下面来详细说明

先说说解题思路，关于这种shift问题有一个很好的表示方法

如以下数列

[4,5,6,1,2,3]，然后对每个数求其(a_index-index+n)%n，最终可发现没个数最后算出的结果都是一样，所以我们可以通过这一性质来容易地表示出shift了几个。

然后下一个性质经过m次两两交换，最多可使得2*m个数字是凌乱的，也就是说至少还有n-2*m个数字还放置它应该所处的位置上

那么，我们可以去枚举shift了几个数字，然后将其反向的shift回去，最后判断其是否可以交换会1 2 3 4 5.....n的顺序，这个判断方式简单的说一下代码如下

bool check(int index){
	vector<int>v;
	v.push_back(0);
	for(int i=index+1;i<=n;i++) v.push_back(p[i]);
	for(int i=1;i<=index;i++) v.push_back(p[i]);
	int tot=0;
	map<int,int>nxt;
	map<int,bool>used;
	for(int i=1;i<=n;i++){
		nxt[i]=v[i];
	}
	for(int i=1;i<=n;i++){
		if(used[i]) continue;
		tot++;
		int now=nxt[i];
		while(!used[now]){
			used[now]=1;now=nxt[now];
		}
	}
	return n-tot<=m;
}

v数组是最后shift回去之后的顺序，然后建立一张图每个i都指向v_i，代表着说目前放在i的数字应该移动到v_i上面去，最后建出来的图每个节点都至多连出一条边，也至多连入一条边，并且连边的点都在环内，假设这个环的尺寸为k，如果想要把这个环内所有数字都正常归位，则需要至少k-1次交换，最后需要总交换就是n-tot(tot是建出来的图里连通块的数量)，最后判断其是否不大于m即可

那还是回归到刚才那个问题，这又枚举又遍历的复杂度不高吗？其实还真就不高，注意之前提到过的性质：经过m次两两交换，最多可使得2*m个数字是凌乱的，也就是说至少还有n-2*m个数字还放置它应该所处的位置上。也就是说当前所枚举的的cnt_shift必须要不小于n-2*m才有可能是我们最后要找的答案，而题目中数据有个看似奇怪的约束0≤m≤n/3，也就是说n-2*m最小不过n/3，而cnt_i(0<=i<n)最后总和等于n，也就是说最后附和条件的cnt_shift不过最多就是3个而已，所以最后输出的可能数字数量也不过最多三个而已，详见以下代码

for(int i=1;i<=n;i++){
		cin>>p[i];
		cnt[(i-p[i]+n)%n]++;
	}
	vector<int>ans;
	for(int i=0;i<n;i++){
		if(n-2*m<=cnt[i]&&check(i)) ans.push_back(i);
	}