[JZOJ5772]【NOIP2008模拟】今天你AK了吗？

Description

AK：All kill
“你为什么没背书？”
“没有为什么，我就是没背书。”
“……我去年买了个表，G—U—N！”
头铁王InFleaKing把背书的时间都拿去列排列了......
n=3的排列一共有六个（顺序按字典序从小到大）：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
气不打一处来的InFleaKing把n的排列打乱了。
他想知道字典序第k小的n的排列是什么？
由于InFleaKing被捉去背书了，所以这个问题只能交给被万人顶礼膜拜的dalao您来解决了。

 

Input

一行，两个数，分别是n,k。
n,k的含义见题目描述。

Output

一行，n个数。
代表字典序第k小的n的排列。
注意两两数之间要用空格隔开。

 

Sample Input

Sample Input1：

1 1

Sample Input2：

2 2

 

Sample Output

Sample Output1：

1

Sample Output2：

2 1

 

 

Data Constraint

【数据约定】
对于10%的数据：1<=n<=3
对于20%的数据，1<=n<=9
对于30%的数据：1<=n<=18，1<=k<=10^6
对于60%的数据：1<=n<=18
对于80%的数据：1<=n<=100,1<=k<=10^100
对于90%的数据：1<=n<=1000,1<=k<=10^1000
对于100%的数据：1<=n<=100000,1<=k<=min(10^20000,n!)

---

直接模拟...不知道为什么讲的这么玄学。

其实是显然的事。

对于从左到右的位置i,前面有(n-1)!种可能...

于是就把剩下的数字中第k / (n - 1)!个数选到当前位置， 然后k %= (n - 1)!，

然后对于后面也是这样。。。

要写高精不开心，直接弃疗，手懒，我是不会写高精的233.

复杂度是O(N^2)的过不去，听讲解的什么奇怪算法不太明白为什么要这么做。

直接用树状数组维护， 再套二分找第k个数就ok了。

复杂度O(Nlog^2N)。

考场上O(N^2)能过不写高精的数据，于是弃疗了没写树状数组套二分。

放上考场60分代码

---

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

inline int read() {

    int res=;char c=getchar();bool f=;

    while(!isdigit(c)) {if(c=='-')f=;c=getchar();}

    while(isdigit(c))res=(res<<)+(res<<)+(c^),c=getchar();

    return f?-res:res;

}

#define ll long long

int n;

unsigned ll k;

int wei[];

unsigned ll fac[];

bool vis[];

int main()

{

    freopen("array.in", "r", stdin);

    freopen("array.out", "w", stdout);

    n = read();

    fac[] = ;

    for (int i =  ; i <= n ; i ++) fac[i] = fac[i-] * i;

    cin >> k;

    k--;

    for (register int i =  ; i < n ; i ++)

    {

        int re,sum = ;

        for (register int j =  ; j <= n; j ++)

        {

            if (sum == k / fac[n-i] + ) break;

            if (!vis[j]) re = j, sum++;

        }

        printf("%d ", re);

        vis[re] = ;

        k %= fac[n-i];

    }

    for (register int i =  ; i <= n ; i ++) if (!vis[i]) return printf("%d", i), ;

    return ;

}