题意：有一棵根为 ，最大深度为 的树，根的深度为 。满足树上每个深度为 的结点有 个儿子。
对每个正整数
求出树上有多少条长度为
的路径。
答案对 取模。
，，时限 。
设 表示对于某一个深度为
的节点 ，长度为 的从 出发向下的路径个数。
是易于计算的，其
记
（即深度为 的节点个数），则
表示以一个深度为 的节点为 的，长度为 的路径条数。
则
乘以对应深度点个数求和即可得到答案。即 ：
对于 ，可以写出：
分两类讨论 ： 直下 / 在该点拐弯。
暴力计算上式是
的，无法通过。
设
，预处理之后 即可 求解答案。
考虑如何从 求出 。
边界为
最终有：
复杂度 。