题解：CF1970E3 Trails (Hard)
inc1ude_c
·
·
题解
给定一 m+1 个点的菊花图，叶子编号为 1\sim m，叶子 i 向根连了 s_i 条双向轻边，l_i 条双向重边，边都有标号，第一天在 1 号点，每天可以选一条边上到根再选一条边下到某一个叶子，但这两条边得至少一条是轻边，问走 n 天的方案数。
建议评蓝或紫。
有一显然 DP：f(i,u) 为到了第 i 天，走到叶子 u 的方案数。
f(i,u)=\sum_vf(i-1,v)\times (s_u(s_v+l_v)+l_us_v)
直接矩阵快速幂只能过 Medium 版本，考虑优化。
f(i,u)=\sum_vf(i-1,v)\times (s_us_v+s_ul_v+l_us_v)
设 w_u=s_u+l_u，则有：
f(i,u)=\sum_vf(i-1,v)\times (w_uw_v-l_ul_v)
写出其转移矩阵
\\f(i,2)
\\\vdots
\\f(i,m)
\end{bmatrix}=
\begin{bmatrix}
w_1w_1-l_1l_1& w_1w_2-l_1l_2& \cdots & w_1w_m-l_1l_m \\
w_2w_1-l_2l_1& w_2w_2-l_2l_2& \cdots & w_2w_m-l_2l_m \\
\vdots & \vdots & \ddots & \vdots \\
w_mw_1-l_ml_1& w_mw_2-l_ml_2& \cdots & w_mw_m-l_ml_m
\end{bmatrix}
\begin{bmatrix}f(i-1,1)
\\f(i-1,2)
\\\vdots
\\f(i-1,m)
\end{bmatrix}
注意到转移矩阵有：
\begin{bmatrix}
w_1w_1-l_1l_1& w_1w_2-l_1l_2& \cdots & w_1w_m-l_1l_m \\
w_2w_1-l_2l_1& w_2w_2-l_2l_2& \cdots & w_2w_m-l_2l_m \\
\vdots & \vdots & \ddots & \vdots \\
w_mw_1-l_ml_1& w_mw_2-l_ml_2& \cdots & w_mw_m-l_ml_m
\end{bmatrix} =
\begin{bmatrix}
w_1 &l_1\\
w_2 &l_2\\
\vdots & \vdots\\
w_m &l_m
\end{bmatrix}
\begin{bmatrix}
w_1 &w_2&\cdots &w_m\\
-l_1 &-l_2&\cdots &-l_m
\end{bmatrix}
换元：
A=B\times C
于是答案为：A^n=(BC)^n=B(CB)^{n-1}C。
而 CB 是一个 2\times 2 的矩阵所以复杂度对了，然后直接写会获得 MLE。
MLE Code
原来 B(CB)^{n-1} 是 m\times 2 的矩阵，而 C 是 2\times m 的矩阵，相乘会得到 m^2 的矩阵。
但不要紧，因为答案只关心该矩阵的第一列。
故最后一次矩阵乘法只算第一列，复杂度就对了。
AC Code