题解 P5919

· · 题解

这题首先不难想到需要每个置换能形成环才能满足 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;
}