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