[NOIP 2004 普及组] 火星人

知识点

排列、字典序、后继排列

解题思路

把当前排列看成全部排列按字典序排列中的一个位置；加M等价于向后移动M次。重复调用next_permutation得到字典序下一个排列，最后按原整数形式输出。

正确性说明

排列与火星数字的对应由字典序定义。next_permutation每次得到严格大于当前排列的最小排列，恰好使位置增加1。重复M次得到要求的位置，题目保证不会超出范围。

易错点

不是把各元素加M；N可以很大，M却不超过100；输出相邻元素用单个空格；不构造N!或整个排列列表。

复杂度

时间O(MN)，额外空间O(1)，输入排列占O(N)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<int>a(n);for(int&x:a)cin>>x;while(m--)next_permutation(a.begin(),a.end());for(int i=0;i<n;++i){if(i)cout<<' ';cout<<a[i];}cout<<'\n';}