自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 21:20:47，当前版本为作者最后更新于2018-10-01 11:37:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单地逛了逛题解区，发现大部分题解分为两种：

• next_permutation
• 手写 next_permutation

于是，我为了不让题解区太单调，也为了拓宽大家的思维，就经过几分钟的努力，想出了一种与众不同的方法。

Updated on 2022.7.14: 添加 $\LaTeX$，增加变进制数加法的讲解。

变进制数

我们的目标是把全排列转化成一个变进制数，以方便我们进行加法。
对于第 $i$ 根手指，它有 $n-i+1$ 种选择，根据位值原理，要想让每个数对应一个全排列，就要让这一位数是 $n-i+1$ 进制的。

那么，整个过程分为三步：

1. 将火星数变成变进制数
2. 将变进制数加上 $m$
3. 将变进制数变成火星数

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

• 首位 $1$ 是 $5$ 种选择 $\{1,2,3,4,5\}$ 的第 $1$ 种，故变为 $0$（从0开始）
• 次位 $4$ 是 $4$ 种选择 $\{2,3,4,5\}$ 的第 $3$ 种，故变为 $2$
• 中间位 $5$ 是 $3$ 种选择 $\{2,3,5\}$ 的第 $3$ 种，故变为 $2$
• 次低位 $2$ 是 $2$ 种选择 $\{2,3\}$ 的第 $1$ 种，故变为 $0$
• 末位 $3$ 是 $1$ 种选择 $\{3\}$ 的第 $1$ 种，故变为 $0$
• 最后，排列 $1,4,5,2,3$ 变成了$(02200)_{unknown}$

接下来给它加上 $3$ 变成 $(02203)$，并处理进位：

• 末位是 $1$ 进制的，进 $3$ 得 $(02230)$。
• 次低位是 $2$ 进制的，满 $2$ 进一得 $(02310)$。
• 中间位是 $3$ 进制的，满 $3$ 进一得 $(03010)$。
• 次位是 $4$ 进制的，$3<4$，不进位，得 $(03010)_{unknown}$。

最后将 $(03010)_{unknown}$ 变回火星数。

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

所以本题答案为 14523 $+3=$ 15243。

代码 $37$ 行，应该是除 STL 外较短的了。

#include<bits/stdc++.h>
using namespace std;
int a[10005];
bool used[10005]={0};
int m,n;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>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>0;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]++;
        cout<<a[i]+1<<" ";
        used[a[i]]=1;
    }
    return 0;
}

这篇题解是我较早时候发的，通过评论区我纠正了举个栗子那个部分的小问题。
现在我也通过评论区知道我这方法叫做康托展开。如果你想了解更多，可以看这篇博客.