2022-10-20

chenhx-xcpc / 2024-11-13 / 原文

跟着 lsy 糊正睿的题（主要是要去看妹子体育节）

》

听 lsy 说 T1T2 很水，就没看，直接看 T3
是计数题，大喜，乍一眼看了没啥思路就开始手玩样例，发现实际上是一坨环之间连边，然后继续分析性质，发现每个环只能向大小是自己大小的因数的环连边，然后考虑 dp ，然后就是以环的大小作为层，同一层要么向以前的层连边，要么在层内连边，然后一开始的想法是先枚举这一层有多少个环是向以前连边的，然后就转换成了一个非常经典的图论问题，就是一个 $n$ 个有标号点的完全图，生成 $m$ 个有根树的方案数，结果以为不大可以使用数学方法算出来，然后就考虑使用 dp ，设 $f[i][j]$ 表示用 $i$ 个点凑出 $j$ 棵树的方案数，每次考虑加点进来，由于有标号需要乘个组合数，利用 P7105 「C.E.L.U-01」门禁 的 trick可以防止算重，然后发现是个类似于背包的转移，且每个物品的贡献只与大小有关，考虑生成函数，而且模数还是 998244353 ，直接上 fft ，结果 lsy 说打不出来（震惊亲妈），然后帮他想 $n^2$ 的，然后还是用上面的状态，结果脑塞了一会，居然不知道怎么办了...，然后过了一会儿发现其实第二维并不重要，第二维的贡献可以在加入背包时计算，然后就混了个 $O(n^2)$ 的背包出来。
赛后看题解，发现就是一开始的思路，那个计数公式好像是什么 广义prufer序列 ，具体的就是一个 $n$ 个有标号点的完全图，生成 $m$ 个有根树的方案数是 ${n-1\choose m-1}\cdot n^{n-m}$，涨鸡屎咯。