2025.7.17-2025.7.18做题记录

2025.7.17-2025.7.18做题记录

只有边权 $0,1$ 时，答案就是邻接矩阵的 $t$ 次幂。

观察到边权很小，暴力拆点，建立分层图。$(i,j)$ 向 $(i,j-1)$ 连边，当有一条权值为 $w$ 的边，$(u,0)$ 连向 $(v,w-1)$，相当于拆成了 $1$ 条 $(u,0)$ 到 $(v,w-1)$ 的路径，$w-1$ 条 $v$ 回到 $(v,0)$ 的路径，然后矩阵快速幂即可。

注意在 $\operatorname{pushdown}$ 中，右子树不能直接套用公式，而应该用整体减去局部，因为右子树不是一个完整的斐波那契数列，没有记录 $a_1 \ a_2$

还可参考代码

高斯消元线性基，将异或换成正常的高斯消元即可

首先，异或运算满足交换律，即顺序不影响结果，所以可以先加入价值大的，后加入价值小的，这样一定是优的。

我是树剖维护链上线性基，线段树暴力合并，复杂度很高，但是过去了。