最新消息:点击查看大S的省钱秘笈

Vijos P1092 全排列 C语言版

Vijos题解 Slyar 50浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

输入两个自然数m,n 1<=n<=20,1<=m<=n!
输出n个数的第m种全排列。
如 :
输入 3 1
输出 1 2 3

输入格式 Input Format

在一行中输入n m

输出格式 Output Format

一个数列,既n个数的第m种排列
每两个数之间空1格

Tip:使用传说中的构造法,纯数学问题。因为数据很大,所以要使用long long类型,我一开始用long没过,换成unsigned long还没过,改成long long才过了。。。汗。。。

#include <stdio.h>

long long jc(int n){
long long x=1;
while (n>0)
x*=(n--);
return x;
}

int main(){
long long s[21];
int i,j,n,m,total,now,b[21]={0};
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++){
total=((m-1)/jc(n-i)+1)%(n-i+1);
if (total==0) total=n-i+1;
now=0;
for (j=1;j<=n;j++){
if (!b[j]) now++;
if (now==total) break;
}
s[i]=j;
b[j]=1;
}
for (i=1;i<=n;i++) printf("%d ",s[i]);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1092 全排列 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. 不懂~ 不过还是学习了~~
    jeedoo7年前 (2009-08-12)回复