CF997D Cycles in product

题意

给你大小为 ​的两棵树 ​，构造一张新图，该图中每一个点的编号为 。如果在 ​中， ​和 ​之间有边，那么在该图上，对于任意 ， 和 之间有边。同样，如果在 ​中， ​和​之间有边，那么在图上，对于任意 ， 和 之间有边
求这个图上长度为 的环有多少个，环可以不为简单环，起始点或方向不同的环视为不同的环

，答案对 取模.

题解

上一个长度为 的环和 上一个长度为 的环以不同方式组合对应图上 个环
即答案为 ，其中 表示 上长度为 的环的个数， 表示 上长度为 的环的个数

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

考虑转移
令 ，有
换根DP维护 ，再通过 计算
足以通过此题

代码 codeforces submission 143516835

优化

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

令 ，有 令 ，有 多项式快速幂和求逆可以做到 的复杂度