一眼 Burnside $dp$
首先置换内部有独立的循环，置换的循环节长度为那些独立循环的 $lcm$
考虑某个循环节长度 $L$ 怎么得到，显然把 $L$ 质因数分解，$\prod_{i=1}^{m}p_i^{k_i}$
那么最优情况下独立循环的循环节为 $p_i^{k_i}$，好像挺显然的
如果 $\sum_{i=1}^{m}p_i^{k_i}$ 还不到 $n$ ，剩下的全部和自己循环就好了
所以就可以 $dp$ 了，设 $f[i][j]$ 表示当前考虑了前 $i$ 个质数，选的质数集合总和为 $j$ 时的方案数
注意上面式子的意义，选的质数集合为若干 $p_i^{k_i}$ 这样的数的集合，并且 $p_i$ 互不相同且包括了当前所有质数且 $k_i>0$，每个数 $p_i^{k_i}$ 只有选或者不选两种情况，并且至少有一个数被选择时的方案数
因为只有这样定义，对于不同的 $j$，它的方案集合才不会重复
那么每次枚举新的 $p_i^{k_i}$ ，有 $f[i][j]=f[i-1][j]+f[i-1][j-p_i^{k_i}]$，$f[i][j]=f[i-1][j]$ 是因为多出来的 $p_i^{k_i}$ 可以不选
并且因为初始只有 $f[0][0]=1$ 所以空集的方案只会算一次
$woc$ 好像就是个背包 $dp$ ？？？
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1007; int n; ll f[N][N],ans; int pri[N],tot; bool not_pri[N]; void pre() { not_pri[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[i]) pri[++tot]=i; for(int j=1;j<=tot;j++) { int g=i*pri[j]; if(g>n) break; not_pri[g]=1; if(!(i%pri[j])) break; } } } int main() { n=read(); pre(); f[0][0]=1; for(int i=1;i<=tot;i++) for(int j=0;j<=n;j++) { f[i][j]=f[i-1][j]; for(int k=pri[i];k<=j;k*=pri[i]) f[i][j]+=f[i-1][j-k]; } for(int i=0;i<=n;i++) ans+=f[tot][i]; printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/LLTYYC/p/11427750.html