P5919 题解

首先注意到一个排列 $p$ 的 order 等于它的所有环长的 $\operatorname{lcm}$，因为每进行一次置换相当于每个环 rotate 一个位置，于是问题转化为求出 $\sum c_i=n$ 使得 $\operatorname{lcm}(c_1,\dots,c_k)$ 最大。

然后考虑这样的问题：要求 order 恰好等于 $x$ ，排列最小长度。

假设我们有一组解 $c_1,\dots,c_k$，可以使用调整法得到最优解：

• $c_i=1$，直接删去这个数，这说明不能有 $1$；
• $c_i=\prod_{i=1}^{m}p_i^{k_i},m>1$，可以将它分为所有的 $p_i^{k_i}$，这说明一个数不能有多个不同质因子；
• $c_i=p^{k_1},c_j=p^{k_2},i\ne j,k_1\le k_2$，删去 $c_i$，这说明同一个质因子的幂只会出现一次。

于是设 $x=\prod_{i=1}^{m}p_i^{k_i}$，则最优解为 $\sum p_i^{k_i}$。

由于互质，问题转化为求出 $\sum c_i=n,\gcd(c_1,\dots,c_k)=1$ 使得 $\prod c_i$ 最大。

然后就可以 dp 了，考虑 dp[i][j] 表示用了前 i 个素数，长度上限为 j ，最大的答案。

转移枚举当前素数不加入或者加入几次方的，乘起来就行，要记录路径。

这个答案可能很大，但是发现 dp 的操作只涉及乘法以及 max ，可以对所有数取 log 计算，由于本题限制特殊不容易卡精度，double 就够用了。

还原路径时还要注意总长度不够要补 1。

最后一个问题就是，知道了所有 $c_i$，怎么构造字典序最小。

考虑从前往后依次填数，最前面肯定贪心填 $2,3,\dots,x,1$ 作为第一个环，然后 $x+2,x+3,\dots,x+y,x+1$ 作为第二个环……

因此把 $c$ 数组从小到大排序然后填进去即可。

复杂度预处理 $O(n\pi(n))$，询问 $O(n)$。

代码

#define db double
const int N=10004,M=200;
int n;
int isp[N],pr[N],cp;
db cln[N];
vi prp[N];
pair<db,int>dp[M][N];
void pre(){
	rept(i,2,N){
		if(!isp[i]){
			pr[cp]=i;
			prp[cp]=vi(1,0);
			for(int j=i;j<N;j*=i)prp[cp].pb(j);
			cln[cp++]=log(i);
		}
		rep(j,cp){
			if(i*pr[j]>=N)break;
			isp[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	rep(i,M)rep(j,N)dp[i][j]={.0,0};
	rep(i,M-1){
		db cc=cln[i];
		rep(j,N){
			rep(k,sz(prp[i])){
				if(j+prp[i][k]>=N)break;
				Mx(dp[i+1][j+prp[i][k]],{dp[i][j].F+cc*k,prp[i][k]});
			}
		}
	}
}
void run(){
	int n;
	cin>>n;
	int cx=M-1,cy=n;
	vi ans;
	while(cx){
		int k=dp[cx][cy].S;
		if(k)ans.pb(k);
		cx--;cy-=k;
	}
	rep(_,cy)ans.pb(1);
	sort(all(ans));
	int cc=1;
	for(int i:ans){
		rept(j,cc+1,cc+i)cout<<j<<" ";
		cout<<cc<<" ";
		cc+=i;
	}
	cout<<"\n";
}

这题首先不难想到需要每个置换能形成环才能满足 $p(p(...(p(i))...))=i$ 成立。

然后 order 是所有环大小的 LCM。

令环的大小为 $x_1x_2...x_k$ （这里为了方便令$x_1 \le x_2 \le ... \le x_k$）其实就是把寻找最大的 $lcm(x_1,x_2,...,x_k)$ 使得 $x_1+x_2+...+x_k=n$。

对于先考虑如何让一个固定的 $x_1,x_2,...,x_k$ 使得字典序最小。

由于是字典序，可以考虑贪心，首先对于一组数 $y_1y_2...y_t$ 满足 $y_1 \le y_2 \le ... \le y_t$）形成的环最小是 $y_2,y_3,...,y_t,y_1$,那么对于多个环，每次应该可以会到$y_1$时就回到$y_1$（可以理解成拿最小的一个环进行贪心）。

很显然，一定存在一个最优解使所有 $x$ 互质（假设$\gcd(x_a,x_b)>1$,则必然存在质因数 $p$ 使$p|x_a$且$p|x_b$,不妨令 $x_b$质因数分解中 $p$的指数更大, 则$x_a,x_b$ 可以改成 $x_a/p,x_b,1,1,1...(x_a-x_a/p$ 个 $1$) 使和、LCM 不变，字典序会更优。

然后发现如果一个数 $x$ 含有超过 $2$ 个质因子它一定不优秀,设他的其中两个质因子为 $p,q$ 其必然能写成 $x=p^a*q^b*c$ 其中能保证 $p^a,q^b*c$ 两部分都 $\ge2$ 所以 $p^a*q^b*c\ge p^a+q^b*c$ （若 $a,b\ge2$ 则 $(a-1)(b-1)\ge1$，则$ab\ge a+b$），则 $x$ 可以改成 $p^a,q^b*c$ 使和不变，LCM 不变差，字典序会更优。

综上，$x_1,x_2,...,x_k$ 为 $1$ 或不同质数次方。

于是可以先筛出 $[2,10000]$ 所有的质数，

然后进行带路径记录的分组背包（可以理解成对于每个质数 $p$ 在 $0,1$、$p,p$、$p^2,p^2...$ 中选一个(当然贡献是相乘的，不是平常背包里的相加）。

这里有两个小细节 :

一，可以采用 long double 来代替高精度，由于只需比较大小，不需输出，所以不需要那么高的精度（实测可以过）。

二，不难发现比较大的质数并不会被选中，我们可以先让程序用 $[2,10000]$ 所有的质数进行 dp，然后再循环出 $[1,10000]$ 所有数中最大可能用到的最大质数 $p_{\max}$，然后再用 $[2,p_{\max}]$ 所有的质数进行 dp 。

最后放一下代码：

#include <bits/stdc++.h>
#define for1(i,n) for(i=1;i<=(n);i++)
#define forlr(i,l,r) for(i=(l);i<=(r);i++)
using namespace std;
typedef long double ld;
const int N=10005,D=10000;
int z[N],cz,n,pre[75][N],T,c[N],cc;
bool b[N];
ld dp[75][N];
int main(){
	int i,j,k;
	forlr(i,2,D){
		if(!b[i]) z[++cz]=i;
		if(cz==72) break;
		for(j=1;z[j]*i<=D;j++){
			b[z[j]*i]=1;
			if(!(i%z[j])) break;
		}
	}
	forlr(i,0,D) dp[0][i]=1;
	for1(j,cz){
		forlr(i,0,D) pre[j][i]=0,dp[j][i]=dp[j-1][i];
		forlr(i,0,D) for(k=z[j];i+k<=D;k*=z[j]) if(dp[j][i+k]<dp[j-1][i]*k)
			pre[j][i+k]=k,dp[j][i+k]=dp[j-1][i]*k;
	}
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);cc=0;
		for(i=cz;i;i--) if(pre[i][n]) n-=(c[++cc]=pre[i][n]);
		sort(c+1,c+cc+1);
		for1(i,n) printf("%d ",i);
		for1(j,cc){
			forlr(k,i,i+c[j]-2) printf("%d ",k+1); 
			printf("%d ",i);i+=c[j];
		}
		puts("");
	}
	return 0;
}