我觉得很有思维含量的一道题

首先根据置换的知识，

每一个置换都可以表示成若干不想交的循环的乘积

所有循环的规模A1+A2+……AK=n

显然要求可能的排数，就是问n拆分成若干个数其可能的最小公倍数的个数

考虑到任意一个数大于1的自然数X一定能这样分解 令p为质数数组

X=p1^m1*p2^m2*…ph*mh

判断X是否可行我们可以想办法构造{Ah}使得其最小公倍数为X

显然{Ah}中pi的指数的最大值是mi

所以，和最小的满足最小公倍数为X的{Ah}是A1=p1^m1 A2=p2^m2 ……Ah=ph*mh（显然每个数都大于等于2）

如果满足A1+A2+……Ah<=n 则X为可行解

因为当A1+A2+……Ah=n 那显然存在可行解

而如果A1+A2+……Ah<n 我们一定可以令Ah+1~Ak全为1，这样最小公倍数不变，也满足了A1+A2+……AK=n

考虑到每一个X都对应唯一的分解质因式，每个分解质因式对应唯一的x

所以我们穷举上述的构造方案所得的最大公倍数一定不遗漏且唯一；

所以，寻找所有可行的X就转化为寻找满足下面条件的方案数

A1+A2+……Ah<=n 

Ai=pi*mi （mi是不确定）

这样我们可用类似背包的方法解决

设f[i,j]表示用前i个质数，对应Ai和为j的方案数

显然f[i,j]=f[i-1,j](这个质数可以不用）+signma(f[i-1,j-p[i]^k]) (j-p[i]^k>=0) (穷举Ai的可能性）；

初始f[0,0]=1;

最后答案就是signma(f[t,i]) 0<=i<=n;

1 var a:array[0..200] of longint; 2     f:array[0..200,0..1010] of int64; 3     i,j,n,t,k:longint; 4     ch:boolean; 5     ans:int64; 6  7 begin 8   readln(n); 9   for i:=2 to n do10   begin11     ch:=true;12     for j:=2 to trunc(sqrt(i)) do   //质数表13       if i mod j=0 then14       begin15         ch:=false;16         break;17       end;18     if ch then19     begin20       inc(t);21       a[t]:=i;22     end;23   end;24   f[0,0]:=1;25   for i:=1 to t do26     for j:=0 to n do27     begin28       f[i,j]:=f[i-1,j];29       k:=a[i];30       while j-k>=0 do31       begin32         f[i,j]:=f[i,j]+f[i-1,j-k];33         k:=k*a[i];34       end;35     end;36   ans:=0;37   for i:=0 to n do38     ans:=ans+f[t,i];39   writeln(ans);40 end.