【题意】
给定一个整数n,求所有n元置换循环最长的长度(即经过多少次置换变回1..n的序列),并输出字典序最小的该方案
【输入】
第一行一个数t表示几组数据
接下来t行每行一个数字表示数字n
【输出】
对于每组数据输出一行,第一个数字表示所有n元置换循环最长的长度,接下来n个数字表示字典序最小的该方案
置换群
dp来解最大值,用f[i][j]表示n=i时分为j个循环的最大值
然后对于每一个询问进行搜索求方案
program poj3590; var all,sum,t,n,i,j,k:longint; ok:boolean; f:array [0..101,0..101] of longint; dl,min:array [0..101] of longint; function max (a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function gcd (a,b:longint):longint; var i:longint; begin while a mod b <> 0 do begin i:=a mod b; a:=b; b:=i; end; exit(b); end; procedure dfs (last,sum,now,tot:longint); var i,j:longint; begin if tot=1 then begin dl[min[n]]:=sum; if sum*now div gcd(sum,now)=f[n,min[n]] then ok:=true; exit; end; for i:=last to sum div tot do if (now mod i = 0)or(gcd(i div gcd (i,now),f[n,min[n]])<>1) then begin dl[min[n]-tot+1]:=i; dfs(i,sum-i,i*now div gcd(i,now),tot-1); if ok then exit; end; end; begin read(t); f[0,0]:=1; for i:=1 to 100 do begin f[i,0]:=1; for j:=1 to i do for k:=0 to i-j do if f[i-j,k]>0 then f[i,k+1]:=max(f[i,k+1],f[i-j,k]*j div gcd(f[i-j,k],j)); end; for i:=1 to 100 do begin min[i]:=0; for j:=i downto 1 do if f[i,min[i]]<f[i,j] then min[i]:=j; if min[i]=0 then min[i]:=i; end; while t>0 do begin read(n); write(f[n,min[n]],' '); sum:=0; ok:=false; dfs(1,n,1,min[n]); for i:=1 to min[n] do begin for j:=sum+1 to sum+dl[i] do if j=sum+dl[i] then write(sum+1,' ') else write(j+1,' '); sum:=sum+dl[i]; end; writeln; dec(t); end; end.