这道题目的基础算法就是**康托展开**
康托展开有着这样的定义——
把一个整数X展开成如下形式:
X = a[n]×(n-1)! + a[n-1]×(n-2)! + ... + a×(i-1)! + ... + a[2]×1! + a[1]×0!
其中，a为整数，并且0<=a<i(1<=i<=n)
可以通过这样的方式求得它的全排列组合，是一种快速便捷、简单便捷的方法。
至于具体的一些细节，你们可以自行搜索一下。
这里，我给出C++的程序（如果使用C的朋友，只要将头文件改成stdio.h即可），希望对大家有所帮助。
**特别注意**：
***我的程序中有输入优化，标准的写法应该差不多是这样的**
```
int s()
{
char ch=getchar();
int x=ch-'0';
for(;(ch=getchar())>='0'&&ch<='9';)
x=x*10+ch-'0';
return x;
}

**我的程序中有输出优化，标准的写法应该差不多是这样的**

bool w(int r)
{
if(r>9)
w(r/10);
putchar(r%10+'0');
return 1;
}
```
我的输入输出优化根据题目需要稍作了修改.
这里，我申明几点。
在一些void的函数内可以尝试改成bool甚至int的返回值，并不影响操作，还更贴近scanf/printf的方式。
输入输出优化是帮助程序在一定程度上节省时间和空间，特别是空间，效果更明显（对，是空间）。

评测结果

编译成功
foo.cpp: In function 'bool permutation(int)':
foo.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
foo.cpp: In function 'int main()':
foo.cpp:42:13: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
k[i]=i;
~~~~^~
foo.cpp:41:20: note: within this loop
for(R int i=1;i<=25;i++)
~^~~~
测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 536 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
Accepted, time = 0 ms, mem = 540 KiB, score = 80

代码

#include<cstdio>
#define R register
#define ll long long
ll n,m,a[25],k[25];
ll s()
{
R char ch=getchar();
R ll x=ch-'0';
for(;(ch=getchar())>='0'&&ch<='9';)
x=x*10+ch-'0';
return x;
}
bool w(R ll r)
{
if(r>9)
w(r/10);
putchar(r%10+'0');
return 1;
}
bool print()
{
for(int i=n;i;i--)
w(a[i]),putchar(' ');
return 1;
}
bool permutation(int w)
{
if(w==0)
return print();
R long long tmp,cnt=1;
for(R int i=2;i<w;i++) cnt*=i;
for(a[w]++;m>cnt;m-=cnt,a[w]++);
tmp=a[w];
a[w]=k[a[w]];
for(R int i=tmp;i<n;i++)
k[i]=k[i+1];
permutation(w-1);
}
int main()
{
for(R int i=1;i<=25;i++)
k[i]=i;
n=s();m=s();
permutation(n);
return 0;
}

希望对大家有所帮助，RP++！

康托展开，注意开long long
十年oi一场空，不开long long见祖宗
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> nums(25), ornums(25);
ll n, m, f[25];
void init() {
f[0] = 1;
for (int i = 1; i < 25; i++)
{
f[i] = f[i - 1] * i;

}
for (int i = 0; i < 25; i++)
{
ornums[i] = i + 1;
}
}
void deal() {
for (int i = 1; i <= n; i++)
{
int k;
k = m / f[n - i];
nums[i] = ornums[k];
m %= f[n - i];
ornums.erase(ornums.begin() + k);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
m--;
init();
deal();
copy(nums.begin() + 1, nums.begin() + n + 1, ostream_iterator<int>(cout, " "));
return 0;
}

.....

.......

要用点排列组合的知识,

如果这个数为 3xxx...x (共n位) ,那这就在 2*(n-1)! ~ 3*(n-1)! 这范围之间

以此类推出第k位来,

仔细调试便能写出正确的程序

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <cstring>

using namespace std;

vector<int> e;
vector<int> res;
int n;
long long m;
long long fac[21];

int c_div(long long a, long long b){
    int res = 0;
    for(; b * res < a; res++);
    return res;
}

int main(){
    cin >> n >> m; fac[0] = 1;
    for(int i = 1; i <= n; i++) e.push_back(i);
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * (long long)i;
    long long r = m;
    for(int i = 1; i <= n; i++){
        int p = c_div(r, fac[n - i]);
        res.push_back(e[p - 1]);
        e.erase(e.begin() + p - 1);
        r -= (long long)(p - 1) * fac[n - i];
    }
    for(int i = 0; i < n; i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}

#include<cstring>
#include<iostream>
using namespace std;
bool b[101];
int i,n,a;
unsigned long long f,m,j,s,k;
unsigned long long aa(int x)
{
int c;
unsigned long long ss=1;
for(c=1;c<=x;c++)
ss*=c;
return ss;
}
main()
{
cin>>n>>m;
memset(b,1,sizeof(b));
for(i=n;i>=1;i--)
{
f=aa(i-1);
j=m/f;
s=0;
if(m!=j*f)
k=j+1;
else
k=j;
if(k==0)
k=i;
for(a=1;a<=n;a++)
if(b[a])
{
s++;
if(s==k)
{
cout<<a;
if(i!=1)
cout<<" ";
b[a]=0;
break;
}
}
m-=j*f;
}
}

模拟 水过

var b:array[0..100]of boolean;n,i,a:longint;f,m,j,s,k:qword;
function js(x:longint):qword;
var c:longint;ss:qword;
begin
ss:=1;
for c:=1 to x do
ss:=ss*c;
exit(ss);
end;
begin
readln(n,m);fillchar(b,sizeof(b),true);
for i:=n downto 1 do
begin
f:=js(i-1);
j:=m div f;
s:=0;
if m<>j*f then k:=j+1 else k:=j;
if k=0 then k:=i;
for a:=1 to n do
if b[a] then
begin
inc(s);
if s=k then
begin
write(a);
if i<>1 then write(' ');
b[a]:=false;
break;
end;
end;
m:=m-j*f;
end;
writeln;
end.

http://hi.baidu.com/jnnewmgzyvbefnd/item/070fa91a13e0e611b93180e9

{康托展开逆运算}
var
jie : array[1..19] of int64;
m : int64;
n,i,j : longint;
have : array[1..20] of longint;
begin
read(n,m);
jie[1] := 1;
for i := 2 to n-1 do jie[i] := jie[i-1] * int64(i);
for i := 1 to n do have[i] := i;
m := m-1;
for j := 1 to n-1 do
begin
write(have[m div jie[n-j] + 1],' ');
for i := m div jie[n-j] + 1 to n-j do have[i] := have[i+1];
m := m mod jie[n-j];
end;
writeln(have[1]);
end.

点击查看程序源码+详细题解

#include

using namespace std;

int number[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

int paixu(int a)

{

int b=1;

for(int i=1;i

var

a:array[0..20] of int64=(1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000);

c,b:array[1..20] of longint;

n,k,i,i1,i2,s,y,j:longint;

begin

readln(n,k);

s:=0;

fillchar(c,sizeof(c),0);

k:=k-1;

j:=n-1;

for i:=1 to n do begin

y:=k div a[j];

for i1:=1 to n do

if c[i1]=0 then begin

s:=0;

for i2:=1 to n do

if c[i2]=0 then

if i1>i2 then s:=s+1;

if s=y then begin

write(i1);

if in then write(' ');

c[i1]:=1;

break;

end;

end;

k:=k mod a[j];

dec(j);

end;

end.

康托展开的逆运算

这个内容我没有在网上找到，不过实现起来并不麻烦，主要还是自己的话应该有很多不严谨之处敬请谅解

这个方法还是用例子来说比较好

例1 {1,2,3,4,5}的全排列，并且已经从小到大排序完毕

(1)找出第96个数

首先用96-1得到95

用95去除4! 得到3余23

用23去除3! 得到3余5

用5去除2!得到2余1

用1去除1!得到1余0

有3个数比它小的数是4

所以第一位是4

有3个数比它小的数是4但4已经在之前出现过了所以是5（因为4在之前出现过了所以实际比5小的数是3个）

有2个数比它小的数是3

有1个数比它小的数是2

最后一个数只能是1

所以这个数是45321

(2)找出第16个数

首先用16-1得到15

用15去除4!得到0余15

用15去除3!得到2余3

用3去除2!得到1余1

用1去除1!得到1余0

有0个数比它小的数是1

有2个数比它小的数是3 但由于1已经在之前出现过了所以是4（因为1在之前出现过了所以实际比4小的数是2）

有1个数比它小的数是2 但由于1已经在之前出现过了所以是3（因为1在之前出现过了所以实际比3小的数是1）

有1个数比它小得数是2 但由于1，3，4已经在之前出现过了所以是5（因为1，3，4在之前出现过了所以实际比5小的数是1）

最后一个数只能是2

所以这个数是14352

#include

#include

using namespace std;

/*

厦门一中信息学小组leap.ahead

VIJOS P1092，题解

*/

long long int jc(long long int a)

{

long long int b = a;

a--;

while(a>0)

{

b*=a;

a--;

}

return b;

}

int main()

{

int n;

int t = 1;

int k = 1;

int p = 0;

long long int m;

cin >> n >> m;

int flaga[n+1];

m--; //step 1

while((n-t)>=1)

{

//cout

康托展开的逆运算

核心代码

m:=m-1;//第k小排列的序号为k-1

for i:= 1 to n do

begin

x = m div (n-i)!//表示数列中有x个数比ans[i]大

m:= m mod (n-i)!//把第i位开始的方案删除

ans[i]:=find(x);//从未用过的数中计算ans[i];

flag[ans[i]]:=true//把得到的ans[i]标记为已经使用

end;

水题

靠，完全没注意n=20,然后通过率就又下了一点......

不是全排列...

AC 70 庆祝一下

刚开始用全排列写的，一个一个找下去，会超时。

于是，我来到了题解，看了整页还是不明白，百度百科上面的也看不懂，这个叫康托展开..

刚开始把m:=m-1;

每次按顺序做这么几件事：1. k:=(m div a[n-i])+1; 2.从前往后找

第k个未使用过的数并标记为已使用，输出 3. m:=m mod a[n-i];

4. 从前往后将未使用过的输出

Program P1092;

Const maxn=21;

Var n,m,i,j,k:longint;

a:array[0..maxn] of int64;

f:array[0..maxn] of boolean;

begin

readln(n,m);

a[1]:=1;

for i:=2 to n do a[i]:=a*i;

fillchar(f,sizeof(f),true);

i:=1;

m:=m-1;

while (m0) and (i0 do

begin

inc(j);

if f[j] then dec(k);

end;

f[j]:=false;

write(j,' ');

m:=m mod a[n-i];

inc(i);

end;

for j:=1 to n do if f[j] then write(j,' ');

readln;

end.