[51NOD1582] [CF514E] N叉树 (Darth Vader and Tree)

题目

51Nod 链接
Codeforces 链接
题目大意为给你一棵无穷深 n 叉树,每个节点的 i 号子节点到父节点的距离为 d_i, 问离根节点距离小于等于 x 的节点有多少个。 (图为 3 3 1 2 3 样例的示意图)

思路

首先可以考虑用 dp 求解。 f[i] 为到根节点距离恰好为 i 的节点数目,s[i] 为到根节点距离小于等于 i 的节点数目。易知 f[i] = \sum f[i - d[j]] ,\ s[i]=\sum f[i]. 但是 x, n 都非常大,但是我们发现 d[j] 小于等于 100, 这意味着,我们更新状态最多只需要前 100 位的信息,意味着,递推式最多维有 100 项的线性递推式,那我们可以考虑用矩阵来解决。
初始矩阵为 F = {\left[ \begin{array}{ccc} f[1] & f[2] & f[3] & ... & f[100] & s[100] \end{array} \right]}
伴随矩阵为 A = { \left[ \begin{array}{ccc} 0 & 0 & 0 & ... & 0 & cnt[100] & cnt[100]\\0 & 1 & 0 & ... & 0 & cnt[99] & cnt[99]\\0 & 0 & 1 & ... & 0 & cnt[98] & cnt[98]\\. & . & . &  & . & . & .\\. & . & . &  & . & . & .\\. & . & . &  & . & . & .\\0 & 0 & 0 & ... & 1 & cnt[1] & cnt[1]\\0 & 0 & 0 & ... & 1 & 0 & 1 \\ \end{array} \right ]}
那么,对于大于 x > 100 我们计算 FA^(x - 100) 就可以得到s[x] 了。
 

代码

 

完结

参考博客链接
再写完的时候,因为想绕过 f[i] 直接表示 s[i], 一度没有思路,写完之后发现 F 矩阵的构造其实可以同时构造多个数列,而不像以前那么死板,也算是学到了😊😊😊😊😊😊😊

发表评论

电子邮件地址不会被公开。 必填项已用*标注