失眠帆布鞋

文章
8
资源
1
加入时间
3年1月23天

514E (矩阵快速幂+DP)

一棵树,每个结点有n个儿子,该第i个儿子到父节点的距离为d[i],问离根节点距离不超过x的结点有多少个,结果对1e9+7取模。之前写的了,忘记是参考哪个大牛的博客了:以下是他的分析 首先注意到每个di  * 用dp[i]表示到根节点长度为i的点的个数, 那么不难发现状态转移方程  * dp[x] = dp[x - 1]*t[1] + dp[x - 2]*t[2] + ... +