火星人

题意：

给定n个数是1-n的排列数，亦或者理解为1-n的置换，然后求向后m个排列数为多少
例如：
1 2 3 4 5 是初始的5个数，让求向后3个的排列数
向后一个：1 2 3 5 4
向后两个：1 2 4 3 5
向后三个：1 2 4 5 3

思路：

给定组合求向后m个排列数 ，dfs(x,f) x代表该填充第x个数，f代表是否从原始的数组转移过来的
当填充到n个数的时候就让m--，当m等于0时输出答案即可。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n;
int a[N];
int ans[N];
int vis[N];
int temp;
bool an=false;

//给定组合求向后m个排列数 
void dfs(int x,bool f){
	
	//若存在即退出 
	if(an) return; 
	if(x>n) {
		temp--;
		if(temp==0) {
				for(int i=1;i<=n;i++) {
				if(i>1) cout<<' ';
				cout<<ans[i];
			}
			puts("");
			an=true;
			return ;
		}
	}
	//枚举每一位的值 
	if(x>n) return ;
	int i;
	if(f) i=a[x];
	else i=1;
	for(;i<=n;i++) {
		if(!vis[i]) {
			vis[i]=1;
			ans[x]=i;
			if(!f) dfs(x+1,f);
			else {
				if(i!=a[x]) dfs(x+1,!f);
				else dfs(x+1,f);
			}
			vis[i]=0;
			ans[x]=0;
		}
	}
	
}

int main()
{
	int m;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
	}
	temp=m+1;
	dfs(1,true);
	
	return 0;
}