数据范围容易想到利用矩阵进行计算。

考虑 $f(k) = (A, B)$ ,其中 $A$ 表示恰好等于 $k$ 的路径条数, $B$ 表示小于等于 $k$ 的路径条数。则可以这样转移: $(A, B) \times (C, D) = (A \times C, B + A \times D)$ 。

需要注意的是,对长度为 $L$ 的路径对答案的贡献可以表示为一个二次多项式(即 $f(L) = L ^ 2$),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

动态 DP 学习笔记

(好懒不想写博客)

把每个点的 dp 转移分成 重儿子 和 自己+轻儿子 两个部分。重儿子的转移把矩阵放树上维护,利用矩阵乘法的性质;轻儿子的转移的每次修改时暴力维护,利用 dp 的性质。详情参考 txc 哥哥的博客

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×