妈妈我终于会这道题了!
设(n)个点的有根仙人掌个数的指数型生成函数(EGF)为(F(x)), 令(f_i = [x^n]F(x))
对于(f_i), 我们考虑钦点(1)号点为根, 然后考虑与(1)相邻的是什么
-
(1)不在环上: 对于这种情况, 我们可以发现与它相邻的还是一颗仙人掌, 于是它的生成函数还是(F(x))
-
(1)不在环上: 对于这种情况, 我们考虑环的大小(i), 那么去除点(1), 它的生成函数就是(F^i(x)), 但是考虑到对称的情况不可取, 实际上它的生成函数是(frac{F^i(x)}{2})
由于点边随意排列均可, 于是有贡献为(exp(F(x) + frac{1}{2}sumlimits_{i geq 2}F^i(x)))
考虑上根, 应该有
([x^n]F(x) = [x^{n-1}](exp(F(x)+frac{1}{2}sumlimits_{i geq 2}F^i(x))) imes n)
于是有
(F(x) = x; exp(F(x) + frac{1}{2}sumlimits_{i geq 2}F^i(x)))
发现(frac{1}{2}sumlimits_{i geq 2}F^i(x) = frac{F^2(x)}{2-2F(x)})
(F(x) = x; exp(frac{2F(x)-F^2(x)}{2-2F(x)}))
接下来我们考虑直接搞一个牛顿迭代, 设(G(F(x)) = x; exp(frac{2F(x)-F^2(x)}{2-2F(x)}) - F(x))
接下来我们有
(F_n(x) = F_{n-1}(x) - frac{G(F_n(x))}{G'(F_n(x))})
于是我们爆算得到
(F_n(x) = F_{n-1}(x) - frac{2x; exp(frac{2F(x)-F^2(x)}{2-2F(x)}) - 2F(x)}{x(1+frac{1}{(F(x)-1)^2}); exp(frac{2F(x)-F^2(x)}{2-2F(x)})-2})
在算出来(F(x))后, 注意到我们F(x)的定义是有根仙人掌个数的指数型生成函数, 为了将其变成无根的, 我们令([x^n]F(x) leftarrow [x^n]F(x) imes frac{1}{n})
接下来我们将其变成荒漠, 这一步我们将(F(x) leftarrow exp(F(x)))即可, 为什么这么是正确的, 我们考虑将(exp(F(x)))展开, 有
(exp(F(x)) = sumlimits{i geq 0} frac{F^i(x)}{i!}), 考虑组合意义, 有([x^n]F^i(x))的意义为选出(n)颗仙人掌并排序得到的, 为了消序除以(n!)即可
然后就是一道多项式板子题了qwq!