矩阵总结
问题形式
- 递推式较大项求值
- 动态 DP
- 图上计数/最优化
做法
- 递推式 & 动态 DP：求出系数矩阵，利用矩阵快速幂进行计算，或使用线段树动态维护
- 图上计数：邻接矩阵的 $k$ 次幂，表示两点间长度为 $k$ 的路径条数。
- 矩阵树定理。
事实上可以通过快速幂优化的不只有一般的矩阵乘法，将矩阵乘法中的 $+$ 和 $\times$ 替换为运算 $\oplus$ 和 $\otimes$，只要求 $\otimes$ 具有结合律、$\oplus$ 具有交换律、$\otimes$ 对 $\oplus$ 具有分配律，也可以类似地计算。
矩阵乘法一般不具有交换律，实现时应当注意乘法顺序。
典例
[ABC236G] Good Vertices
求某个点到所有点的经过恰好 $L$ 条边的最小瓶颈路长度。
对邻接矩阵定义广义矩阵乘法 $\circ$：
$$\displaylines{(A\circ B)_{i,j}=\min_k\{\max(A_{i,k},B_{k,j})\} }$$不难发现 $({A^k})_{i,j}$ 表示点 $i$ 到 $j$ 的长为 $k$ 的瓶颈路长度。