Matrix

CF 166E Tetrahedron

  • dp方程设为 f[i] 最后在 D点，g[i] 表示最后不在D点。最后 g[] 可以通过矩阵加速数列求得，数据可以强化，复杂度 \(O(logn)\)

CF 1252K Addition Robot

  • 套路题。线段树上的点用一个可以表示运算的矩阵代替，线段树维护区间乘。因为修改就是A，B互换，保存两种情况的矩阵即可。被ygt大佬秒切了呜呜呜