题解

思路1

这是最常用的思路，我们观察可以发现这是一个全排列，$+ 1$ 就相当于下一个全排列。

我们可以用系统函数next_permutation：

#include<bits/stdc++.h>
using namespace std;
int n, m, ord[10005];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	    scanf("%d", &ord[i]);
	for (int i = 1; i <= m; i++)
	    next_permutation(ord + 1, ord + n + 1); // +1
	for (int i = 1; i <= n; i++)
	    printf("%d ", ord[i]);
	printf("\n");
	return 0;
}

当然你也可以选择手写，用dfs，这里就不出示代码了。

思路2

我们没事找事拓宽思维，可以把全排列转换为变进制数。

对于第 $i$ 根手指，它有 $n-i+1$ 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 $n-i+1$ 进制的。

之后我们把变进制数加上 $m$，再转换回来，就可以了。

我们来看一个实例： 将 $1,4,5,2,3$ 变成变进制数：

• 第 $1$ 位 $1$ 有 $5$ 种选择 $\{1,2,3,4,5\}$ 的第 $1$ 种，故变为 $0$（从0开始）
• 第 $2$ 位 $4$ 有 $4$ 种选择 $\{2,3,4,5\}$ 的第 $3$ 种，故变为 $2$
• 第 $3$ 位 $5$ 有 $3$ 种选择 $\{2,3,5\}$ 的第 $3$ 种，故变为 $2$
• 第 $4$ 位 $2$ 有 $2$ 种选择 $\{2,3\}$ 的第 $1$ 种，故变为 $0$
• 第 $5$ 位 $3$ 有 $1$ 种选择 $\{3\}$ 的第 $1$ 种，故变为 $0$

最后，排列 $1,4,5,2,3$ 变成了 $(02200)_{5, 4, 3, 2, 1}$

$(02200)_{5, 4, 3, 2, 1} + (3)_{10}$，根据每一位的进制进位：

• 第 $5$ 位是 $1$ 进制的，进 $3$ 得 $(02230)$。
• 第 $4$ 位位是 $2$ 进制的，满 $2$ 进 $1$ 得 $(02310)$。
• 第 $3$ 位是 $3$ 进制的，满 $3$ 进 $1$ 得 $(03010)$。
• 第 $2$ 位是 $4$ 进制的，$3<4$，不进位，得 $(03010)_{5, 4, 3, 2, 1}$

我们将他变回火星数：

• 第 $1$ 位 $0$ 表示这位应选择 $\{1,2,3,4,5\}$ 的第 $1$ 种，即 $1$
• 第 $2$ 位 $3$ 表示这位应选择 $\{2,3,4,5\}$ 的第 $4$ 种（$1$ 被选过了），即 $5$
• 第 $3$ 位 $0$ 表示这位应选择 $\{2,3,4\}$ 的第 $1$ 种，即 $2$
• 第 $4$ 位 $1$ 表示这位应选择 $\{3,4\}$ 的第 $2$ 种，即 $4$
• 第 $5$ 位 $0$ 表示这位应选择 $\{3\}$ 的第 $1$ 种，即 $3$

其实这也叫康托展开。

最后写出代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, a[10005];
bool used[10005] = {0};
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        int x = a[i];
        for (int j = 1; j <= a[i]; j++)
            x -= used[j];
        used[a[i]] = 1;
        a[i] = x - 1;
    }
    a[n] += m;
    for (int i = n; i >= 1; i--)
    {
        a[i - 1] += a[i] / (n - i + 1);
        a[i] %= n - i + 1;
    }
    memset(used, 0, sizeof(used));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0;j <= a[i]; j++)
            if (used[j])
                a[i]++;
        printf("%d ", a[i] + 1);
        used[a[i]] = 1;
    }
    printf("\n");
    return 0;
}