noip模拟 *置换

暴力就是枚举每种情况，算 \(lcm\)。

然后仔细想想（虽然考场没想）就会发现，最后图会形成若干个环

我们要求的其实就是环大小的 \(lcm\)

根据这个性质，可以得到一个 \(60\) 分的 \(dp\)

令 \(dp_{i,j}\) 表示一共选了 \(i\) 个数，\(lcm\) 为 \(j\) 的方案数

我们枚举环的大小 \(s\) 和数量 \(a\)，可以转移

\[dp_{i+s*a,lcm(j,s)}=dp_{i,j}*\prod_{z=1}^{a}\binom{i+s*z}{s}(a!)^{-1}*((s-1)!)^{a}

\]

转移的第二项是在求选数的方案，最好自己理解一下

第三项是求单位环连边的方案

\(lcm\) 过大（状态数太大），在写 \(60\) 分的时候还要写 \(vec\)

考虑怎么优化

把一个 \(lcm\) 拆成若干质因子，发现大于 \(\sqrt{n}\) 的质因子出现次数不会大于 \(1\)

那我们把所有小于 \(\sqrt{n}\) 的质因子可以构成的 \(lcm\) 处理出来，发现数量不超过 \(2000\) 个

那这道题就可以做了

处理出每个数被小于 \(\sqrt{n}\) 的质因子处理尽的值（设其为 \(t\) ），把 \(t*t\) 乘进方案就好了

因为 \((ab)^2=a^2b^2\)

Code