鸽子写题了！！！
有个东西叫 Euler 变换。
似乎也叫做 Polya Exp 或者 Multiset 构造？
具体地，对于 {fi} 的 OGF F(x)，其 Euler 变换是这样的： E(F(x))=∞∏i=11(1−xi)−fi
做过付公主的背包或者遗忘的集合的同学应该很熟悉这个东西？
因为实际上就是背包，所以相当于 OGF 的 exp。
然后通过一些代数推导 E(F(x))=∞∏i=11(1−xi)−fi=exp(∞∑i=1−filn(1−xi))=exp(∞∑i=1fi∞∑t=1xitt)=exp(∞∑t=11t∞∑i=1fixit)=exp(∞∑t=1F(xt)t)
Polya 的推导还不会……什么时候把群论学好了再回来填坑。
设无标号有根树的 OGF 为 F(x)，可以列出方程 F(x)=xE(F(x))
可以两边求导得到 F′(x)=(xE(F(x)))′=E(F(x))+x(E(F(x)))′=E(F(x))+xexp(∞∑t=1F(xt)t)(∞∑t=1F(xt)t)′=F(x)x+F(x)∞∑t=1F′(xt)xt−1
然后可以直接分治 NTT 解决。
但这样不好玩。
考虑牛顿迭代。
为了规避常数爆炸的 exp，可以将方程化为以下形式 lnF(x)x−∞∑t=1F(xt)t=0
考虑设 G(x)=F(x)x，H(G(x))=lnG(x)−∞∑t=1xtG(xt)t，那么便是要解 H(G(x))=0
但是你可能会说后面那一大坨怎么办呢？
考虑平时牛顿迭代的过程：求得 G0(x) 满足 H(G0(x))≡0(modxn)
然后求 G(x)≡G0(x)−H(G(x))H′(G(x))(modx2n)
于是注意到，在我们求 G(x) 时，∞∑t=2xtG(xt)t 是可以得知的。
所以用 ∞∑t=2xtG0(xt)t 替换之，并视为一个常数。
从而 H(G(x))=lnG(x)−xG(x)−∞∑t=2xtG0(xt)t
且 H′(G(x))=1G(x)−x
牛顿迭代即可。
但是题目要求的貌似是无根树呢……
考虑钦定一个特殊的点为根，比如重心。
然后用 fn 减去根不是重心的情况。
根不是重心当且仅当其中一个子树的大小超过了 ⌊n2⌋，于是答案为 fn−n−1∑i=⌊n2⌋+1fifn−i
不过，当 n 为偶数时，可能存在两个重心。
即存在一个子树大小恰为 n2。
如果这棵子树和其他部分完全同构，那么只会被计算一次。
否则会重复算，需要减去。
此时答案为 fn−n−1∑i=n2+1fifn−i−(fn22)
代码：
1 |
|