生成函数练习

· · 题解

最近一直在尝试用生成函数做题，但推到半路总会感觉力不从心……

总之多练吧，相信练得多了会有好结果的。

转换一下题目，相当于给你一棵树，有 k 个关键点，选 k 个不交集合使得每个集合的 LCA 是对应关键点，问方案数。

用组合类描述。组合对象的大小显然就是剩余点数量。

非关键点的转移比较简单。令 H_u(x)=\prod_v F_v(x)，有 F_u(x)=xH_u(x)。

关键点分两种转移：

当关键点必选时，每个儿子的剩余点有选不选两种，用 H_u(x+1) 描述。

当关键点不选时，考虑容斥。总方案 H_u(x+1)，减去一个都不选的方案 H_u(x)，减去只挑一个儿子的方案。只挑一个儿子相当于这个儿子不选空集，其它儿子选空集，所以转移综上：

F_u(x)=H_u(x+1)+x\left[H_u(x+1)-H_u(x)-\sum_v(F_v(x+1)-F_v(x))\prod_{w\ne v}F_w(x)\right]

稍微化简一下。

F_u(x)=(x+1)H_u(x+1)+xH_u(x)\left(son_{u}-1-\sum_v\frac{F_v(x+1)}{F_v(x)}\right)

下一步经典操作：注意到答案是 F_1(1)，非关键点转移只考虑 x，关键点转移考虑 x 和 x+1。但是关键点只有 k 个啊。

所以对于每个点咱直接维护 F_u(x),x\in[1,k] 即可，上述柿子立马变得和蔼可亲了起来。

于是轻松给出 O(nk) 做法。

显然咱不需要止步于此。

非关键点的转移实在是太简单了，没有关键点的子树方案直接就是 x^{sz_u}。

只有一个子树有关键点的转移也很简单，都是 x^c 的形式。

所以咱建虚树，只有虚树节点需要上述转移。

愿意的话虚树都不用建，因为非关键点就是对位乘。

将 n 个点分给 k 个关键点的空子树，每个关键点的空子树大小本质不同的只有 \sqrt{kn}。

快速求幂的话可以光速幂，追求常数可以离线下来线性筛。

复杂度 O(k\sqrt{kn}+k^2+n)。

或许与题解区的组合或容斥做法本质一样，但咱作为 baka 肯定是搞不懂这些东西滴~

代码为目前最优解，有需求私。