2025.7.17-2025.7.18做题记录

· · 个人记录

2025.7.17-2025.7.18做题记录

高斯消元，矩阵

P4159 [SCOI2009] 迷路

只有边权 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) 的路径，然后矩阵快速幂即可。

CF446C DZY Loves Fibonacci Numbers

题解

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

P9382 [THUPC 2023 决赛] Freshman Dream

题解

还可参考代码

线性基

Odd Subrectangles

题解

自己的题解

P3265 [JLOI2015] 装备购买

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

P4570 [BJWC2011] 元素

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

P3292 [SCOI2016] 幸运数字

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

正解