【题解】P6132 [集训队互测 2019] 简单计数

https://www.luogu.com.cn/problem/P6132

人话：有标号根向森林，一个森林的系数为 \(k^{\mathrm{cntEdge}}\)，要求每个点入度在集合 \(S\) 内。\(S\subseteq\{0,1,2,3\}\)。

首先必须有 \(0\in S\)，否则一定存在环。

森林：\(F(x)=x\sum_{i\in S} \frac{F^i(x)}{i!}\)。
拉格朗日反演：\(x=G(x)\sum_{i\in S}\frac{x^i}{i!}\Rightarrow G(x)=\frac{x}{\sum_{i\in S} \frac{x^i}{i!}}\)。
\([x^n]F^k(x)=\frac{k}{n}[x^{n-k}](\frac{x}{G(x)})^n=\frac{k}{n}[x^{n-k}](\sum_{i\in S}\frac{x^i}{i!})^n\)，令 \(\mathcal{S}(x)=\sum_{i\in S}\frac{x^i}{i!}\)。

答案就是 \(n!\sum_{i=1}^{n} \frac{k^{n-i}}{i!}[x^n]F^i(x)=n!\sum_{i=1}^{n} \frac{k^{n-i}}{i!}\cdot\frac{i}{n}[x^{n-i}]H(x)=\sum_{i=0}^{n-1}(n-1)^{\underline i}k^i[x^i]\mathcal{S}^n(x)=\sum_{i=0}^{n-1} \binom{n-1}{i}k^i[\frac{x^i}{i!}]\mathcal{S}^n(x)=[\frac{x^{n-1}}{(n-1)!}]e^x\mathcal{S}^n(kx)\)。

求导后整理系数，可以写出答案 \(ans_t\) 的递推式：\(ans_t=\sum_{i\in S} k^i\binom{t-1}{i}ans_{t-i-1}+\sum_{i\in S,i\ne 0} k^i(\binom{t-1}{i-1}(n+1)-\binom{t}{i})ans_{t-i}\)。
转移系数是关于 \(t\) 的低阶多项式，可以使用整式递推处理，复杂度 \(O(\sqrt n\log n)\)。