题目大意
请你输出字典序第 \(k\) 小的 \(n\) 的全排列。
对于 \(100\ \%\) 的数据：\(1 \leq n \leq 100000，1 \leq k \leq min(10^{20000}，n!)\)
解题思路
\(30 \ pts\) 做法：dfs 暴力，这不用多说了吧，大家应该都会，毕竟是入门时做过的题，好像还可以用那个 next_permutation 做，跟 dfs 时间复杂度一样，为 \(O(n!)\)。
\(60 \ pts\) 做法：逆康拓展开。
\(100 \ pts\) 做法：压位高精，树状数组维护查询。
AC CODE
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int MAXN = 1e5 + 5;
int n, len;
int a[MAXN], mod[MAXN], c[MAXN];
char k[MAXN];
int div(int x)
{
int r = 0;
for (int i = len; i >= 0; i--)
{
int s = r * (int)(1e13) + a[i];
a[i] = s / x;
r = s % x;
}
while (!a[len]) len--;
return r;
}
void update(int x)
{
for (int i = x; i <= n; i += i & -i) c[i]++;
}
int query(int x)
{
int res = 0;
for (int i = x; i; i -= i & -i) res += c[i];
return res;
}
signed main()
{
scanf("%lld%s", &n, k);
len = strlen(k);
int pos = 0;
for (int i = len - 1; i >= 0; i--)
{
if ((len - i - 1) % 13 == 0) pos++;
mod[i] = pos - 1;
}
for (int i = 0; i < len; i++) a[mod[i]] = a[mod[i]] * 10 + k[i] - ‘0‘;
a[0]--;
for (int i = 0; i < len; i++)
if (a[i] < 0)
{
a[i + 1]--;
a[i] += (int)(1e13);
}
len = pos - 1;
for (int i = 1; i <= n; i++)
mod[n - i + 1] = div(i);
for (int i = 1; i <= n; i++)
{
int l = 1, r = n, ans = 0;
while (l <= r)
{
int mid = (l + r) >> 1;
int x = mid - query(mid);
if (x <= mod[i])
{
l = mid + 1;
}
else
{
ans = mid;
r = mid - 1;
}
}
update(ans);
printf("%lld ", ans);
}
return 0;
}