CF997D Cycles in product

题意

给你大小为 $n_1, n_2$​的两棵树 $T_1, T_2$​，构造一张新图，该图中每一个点的编号为 $(u,v)$。如果在 $T_1$ ​中， $u_1$ ​和$u_2$ ​之间有边，那么在该图上，对于任意 $1\le v\le n_2$，$(u_1, v)$ 和 $(u_2, v)$ 之间有边。同样，如果在 $T_2$ ​中，$v_1$ ​和$v_2$​之间有边，那么在图上，对于任意 $1\le u\le n_1$，$(u, v_1)$ 和 $(u, v_2)$ 之间有边
求这个图上长度为 $K$ 的环有多少个，环可以不为简单环，起始点或方向不同的环视为不同的环

$n_1, n_2\le 4000, K\le 75$，答案对 $998244353$ 取模.

题解

$T_1$ 上一个长度为 $K_1$ 的环和 $T_2$ 上一个长度为 $K_2$ 的环以不同方式组合对应图上 $\begin{pmatrix}K_1+K_2\\k_1\end{pmatrix}$ 个环
即答案为 $\sum\limits_{0\le i\le K}F1_i\times F2_{K-i}\times\begin{pmatrix}K\\i\end{pmatrix}$，其中 $F1_i$ 表示 $T_1$ 上长度为 $i$ 的环的个数，$F2_i$ 表示 $T_2$ 上长度为 $i$ 的环的个数

我们把每个点作为起始点分别计算，考虑到树上所有的环长度均为偶数，令 $f_{u, k}$ 表示以 $u$ 为起始点，长度为 $2\times k$ 的环的个数，有 $F_{2\times k}=\sum\limits_u f_{u, k}$
由于从父亲节点往儿子节点转移十分困难，不妨对于每个点只考虑在其子树中的环然后换根DP

考虑转移
$$f_{u,k}=\sum_{0\le t<k}f_{u,t}\sum_{v\in \text{son}_u}f_{v,k-t-1}$$ 令 $h_{u,k}=\sum\limits_{v\in \text{son}_u}f_{v,k-t-1}$，有
$$f_{u,k}=\sum_{0\le t<k}f_{u,t}\times h_{u, k-t-1}$$ 换根DP维护 $h$，再通过 $h$ 计算 $f$
$\Theta((n_1+n_2)\times K^2)$ 足以通过此题

代码 codeforces submission 143516835

优化

复杂度瓶颈在 $f$ 的计算，考虑优化这一过程

令 $h'_{u,k}=h_{u,k-1}$，有 $$f_{u,k}=\sum_{0\le t<k}f_{u,t}\times h'_{u,k-t}$$ 令 $G_u(x)=\sum_{1\le i\le k}h'_{u,i}\times x^i$，有 $$\begin{aligned}f_{u,k}&=[x^k]\sum_{1\le i\le k}G_u(x)^i\\&=[x^k]\frac{G_u(x)^{k+1}-G_u(x)}{G_u(x)-1}\end{aligned}$$ 多项式快速幂和求逆可以做到 $\Theta((n_1+n_2)K\log K)$ 的复杂度