Codeforces 1279E New Year Permutations
题目链接
https://codeforces.com/contest/1279/problem/E
题目大意
感觉这个题意非常不好叙述……
大概意思是一个排列，按下标和数值连边建图，会形成若干个环，将每一个环按最大表示之后重新按顺序写下来形成一个新的排列。如果这个新的排列和原来的排列一样的话，那么称这个排列是美丽的。求长度为 $n$ 且字典序为 $k$ 的排列。
题目分析
首先考虑如何才能让一个排列是美丽的。由于每一个环都要重新按顺序放置，因此一个环上的东西应该是连着的，否则一定在重新排序之后会变换位置。再来考虑每一个环，因为要按最大表示来书写，因此第一个元素一定是这个环中的最大的。
现在先来考虑一个开头为 $n$ 的长度为 $n$ 的排列有多少种可能。显然如果这样的话点 $1$ 和 $n$ 已经相连，那么显然剩下的元素任何一种不同的排列都可以构成一个满足要求的环。也就是说可以构成的排列共 $(n – 2)!$ 个（特判长度为 $1$ 的序排列）。
那么这样一来一个简单的 $O(n^2)$ $DP$ 就可以求出长度为 $n$ 的排列共有多少个是美丽的。
这样一来就可以使用数位 $DP$ 先把所求排列分成若干个子排列，并且能知道每一个排列在该长度下的字典序大小。因为每一个子排列中所有的元素都是连续的，因此可以统一成一个问题。
这时候再来考虑如何求长度为 $n$ 的开头为 $n$ 且字典序为 $k$ 的排列大小。考虑一个已确定的长度为 $x$ 的合法前缀，求后续有多少个可行排列。显然每填写一个数都会连一条边，那么相当于其实已经删掉了一个点。那么只需要考虑已确定开头，剩余 $n – x$ 个点有多少个排列。那么显然答案为 $(n – x – 1)!$。由此看来不管怎么填写，不需要考虑后续填写的可行性，后面的可能填写方式的数量都一样。这样一来又可以数位 $DP$ 了。使用并查集维护一下可行性即可。
将每一个子排列填写完再一起输出即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
long long inf = 2e18;
long long t;
long long n;
long long m;
long long fac[maxn];
long long f[maxn];
long long fr[maxn];
bool vis[maxn];
int fa[maxn];
long long mul(long long x, long long y){
long long ret = x * y;
if(ret >= inf or ret / x != y) ret = inf;
return ret;
}
long long calc(long long x){
if(x == 1) return 1;
return fac[x - 2];
}
int init(int n){
for(int i=1;i<=n;i++)fa[i] = i;
return 0;
}
int find(int x){
if(fa[x] != x){
fa[x] = find(fa[x]);
}
return fa[x];
}
vector <long long> getn(long long x, long long y){
vector <long long> ret;
init(x);
memset(vis, 0, sizeof(vis));
ret.push_back(x);
fa[x] = 1;
vis[x] = true;
long long z = x - 3;
y++;
for(long long i=1;i<x;i++){
for(long long j=1;j<=x;j++){
if(!vis[j] and i == x - 1){
ret.push_back(j);
break;
}
if(find(i + 1) == find(j) or vis[j]) continue;
if(z < 0) z = 0;
if(fac[z] >= y){
z--;
ret.push_back(j);
vis[j] = true;
fa[find(j)] = find(i + 1);
break;
}else{
y -= fac[z];
}
}
}
return ret;
}
int main(){
long long i, j;
long long x, y;
fac[0] = 1;
for(i=1;i<=50;i++){
fac[i] = fac[i - 1] * i;
if(fac[i] >= inf or fac[i] / i != fac[i - 1]){
fac[i] = inf;
}
}
f[0] = 1;
for(i=1;i<=50;i++){
for(j=0;j<i;j++){
f[i] = f[i] + mul(f[j], calc(i - j));
if(f[i] >= inf)f[i] = inf;
}
}
scanf("%lld", &t);
while(t--){
scanf("%lld%lld", &n, &m);
if(m > f[n]){
printf("-1\n");
continue;
}
vector <long long> vec;
vector <long long> num;
long long l = 0;
for(i=1;i<=n;i++){
if(mul(calc(i - l), f[n - i]) >= m){
vec.push_back(i - l);
num.push_back((m - 1) / f[n - i]);
m = (m - 1) % f[n - i] + 1;
l = i;
}else{
m -= mul(calc(i - l), f[n - i]);
}
}
long long sum = 0;
for(i=0;i<vec.size();i++){
x = vec[i];
y = num[i];
vector <long long> tmp = getn(x, y);
for(auto y : tmp){
printf("%lld ", y + sum);
}
sum += x;
}
printf("\n");
}
return 0;
}