矩阵乘法及广义矩阵乘法
前置知识：矩阵相关基础概念。
记 \(A(i, j)\) 表示矩阵 \(A\) 的第 \(i\) 行第 \(j\) 列， \(n_A\) 为 \(A\) 的行数， \(m_A\) 为 \(A\) 的列数。
定义矩阵加法 \(A+B\) 为（ \(n_A=n_B,m_A=m_B\)）：
矩阵加法有交换律，结合律。
定义矩阵乘法 \(A\times B\) 为（ \(m_A=n_B\)）：
矩阵乘法满足结合律，对矩阵加法的分配律，但不满足交换律。
定义关于运算 \((\oplus, \otimes)\) 广义矩阵乘法 \(A\times B\) 为（ \(m_A=n_B\)）：
若其存在结合律，则：
\[\ \ \ \ \ \begin{aligned}(AB)C & = A(BC) \\ \bigoplus_{k=1}^{m_B}(\bigoplus_{p=1}^{m_A}(A(i,p)\otimes B(p,k))\otimes C(k,j)) & =\bigoplus_{k=1}^{m_A}(A(i,k)\otimes \bigoplus_{p=1}^{m_B}(B(k,p)\otimes C(p,j))) \end{aligned} \]若：
- \(\otimes\) 对 \(\oplus\) 有（左、右）分配律；
- \(\otimes\) 有结合律；
- \(\oplus\) 有交换律。
则有：
即满足结合律。
常见的 \((\oplus, \otimes)\) 组合有： \((+,\times)\) ， \((\max, +)\)。
练习题目：
- B2104 矩阵加法
- B3615 测测你的矩阵乘法
- P3390 【模板】矩阵快速幂
矩阵递推
矩阵可以有效地解决线性组合问题。
斐波那契问题：\(fib_{k}=fib_{k-1}+fib_{k-2}\)，求 \(fib_{n}\)。
我们构造矩阵 \(f_{k-1}=\begin{bmatrix}fib_{k-1}&fib_{k-2}\end{bmatrix}\)（注意下标）。
则 \(f_{k}=f_{k-1}\times \begin{bmatrix}1&1\\1&0\end{bmatrix}\)。
这样我们就可以用另一种方式 \(O(2^3 n)\) 递推出 \(fib_{n}\)。
注意到这样递推每一项的转移都是一样的，而又知道矩阵有结合律，故 \(f_{k}=f_1\times \begin{bmatrix}1&1\\1&0\end{bmatrix}^{k-1}\)。
矩阵显然可以使用快速幂，故可以 \(O(2^3\log n)\) 递推出 \(fib_n\)。
那么，现在你已经对矩阵递推有一定的了解了，就让我们看一看下面这个简单的例子，来把我们刚刚学到的知识运用到实践中吧！
\[\boxed{\text{试试看！}\\\text{例题1.7}} \]洛谷 P1707 刷题比赛
第 \(1\) 天 A,B,C 都做了 \(1\) 道题。第 \(2\) 天 A,B,C 都做了 \(3\) 道题。
A 同学第 \(k+2\) 天刷题数量 \(a_{k+2}=pa_{k+1}+qa_k+b_{k+1}+c_{k+1}+rk^2+tk+1\)；
B 同学第 \(k+2\) 天刷题数量 \(b_{k+2}=ub_{k+1}+vb_k+a_{k+1}+c_{k+1}+w^k\)；
C 同学第 \(k+2\) 天刷题数量 \(c_{k+2} = xc_{k+1}+yc_k + a_{k+1} + b_{k+1} + z^k+k+2\)。
给定 \(n\leq 10^{16}\) 和其它常数，求出 \(a_n,b_n,c_n\)，答案取模。
构造矩阵 \(f_{k-1}=[a_{k-1}, a_{k-2}, b_{k-1}, b_{k-2}, c_{k-1}, c_{k-2}, k-2, (k-2)^2, 1, w^{k-2}, z^{k-2}]\)。
则有：\(f_{k} = f_{k-1}\times \begin{bmatrix} p&1&1&0&1&0&0&0&0&0&0\\ q&0&0&0&0&0&0&0&0&0&0\\ 1&0&u&1&1&0&0&0&0&0&0\\ 0&0&v&0&0&0&0&0&0&0&0\\ 1&0&1&0&x&1&0&0&0&0&0\\ 0&0&0&0&y&0&0&0&0&0&0\\ t&0&0&0&1&0&1&2&0&0&0\\ r&0&0&0&0&0&0&1&0&0&0\\ 1&0&0&0&2&0&1&1&1&0&0\\ 0&0&1&0&0&0&0&0&0&w&0\\ 0&0&0&0&1&0&0&0&0&0&z\end{bmatrix}\)。
则 \(f_{k} = f_{2} \times B^{k-2}\) （ \(B\) 是转移的矩阵）。
对矩阵进行快速幂即可 \(O(11^3\log n)\) 解决。
https://www.luogu.com.cn/paste/u9m7bjru
总结：矩阵递推可以做的有：
- 需要加前 \(t\) 项的 dp 值（乘系数），每个函数消耗 \(t\) 个矩阵空位。
- 需要加常数，消耗 \(1\) 空位。
- 需要加下标（\(\pm \Delta\)），消耗 \(1\) 空位。
- 需要加常数的下标（\(\pm\Delta\)）次方，消耗 \(1\) 空位。
- 需要加下标（\(\pm\Delta\)）的 \(t\) 次方，消耗 \(t+1\) 空位（利用二项式定理）。
其中 \(\Delta\) 需恒定。以上空位的消耗会有重叠。
练习题目：
- P1939 【模板】矩阵加速（数列）
- P1349 广义斐波那契数列
- P3758 [TJOI2017]可乐
- P2109 [NOI2007] 生成树计数
运用矩阵解决线性组合问题
P3373 【模板】线段树 2
区间加，区间乘，区间求和， \(n,m\leq 10^5\)。
使用线段树维护。普通的懒标记太麻烦了，故使用矩阵求解。
构造一个节点的矩阵 \(f_{k}=\begin{bmatrix}\sum val& r-l+1\end{bmatrix}\) ，则 \(f_{k}=f_{lson}+f_{rson}\) 。
构造一个节点的懒标记矩阵 \(lazy_{k}\)，初始 \(=\begin{bmatrix}1&0\\0&1\end{bmatrix}\) 即单位元。
则对于区间加 \(z\) 操作，则对于需要操作的节点， \(lazy_{k}\xleftarrow {\times}\begin{bmatrix}1&z\\1&0\end{bmatrix},f_{k}\xleftarrow {\times}\begin{bmatrix}1&z\\1&0\end{bmatrix}\) 。
对于区间乘 \(z\) 操作，则对于需要操作的节点， \(lazy_{y}\xleftarrow {\times} \begin{bmatrix}z&0\\1&0\end{bmatrix},f_{y}\xleftarrow {\times}\begin{bmatrix}z&0\\1&0\end{bmatrix}\) 。
下放时设置 \(f_{son}\xleftarrow {\times} lazy_{k},lazy_{son}\xleftarrow {\times} lazy_{k}\) 即可，和普通线段树大体没有区别。
至此我们可以使用 \(2^3\) 的常数解决原来复杂的懒标记下传（把矩阵乘法循环展开就和原来常数差不多了qwq）。
https://www.luogu.com.cn/paste/ulndkmq8
接下来本质理解一下这种做法。
U226931 Linear function？（原创题，可提交，不卡常（？））
\(n\) 节点的树，每个节点有 \(x_i,y_i,z_i\)> 三个权值。
操作 \(1\)：对于所有 \(s,t\) 路径上的节点，\(x_i\leftarrow ax_i+by_i+cz_i+d\)。
操作 \(2\)：对于所有 \(s,t\) 路径上的节点，\(y_i\leftarrow ax_i+by_i+cz_i+d\)。
操作 \(3\)：对于所有 \(s,t\) 路径上的节点，\(z_i\leftarrow ax_i+by_i+cz_i+d\)。
操作 \(4\)：求出 \(s,t\) 路径上 \(x_i+y_i+z_i\) 之和。
\(n,m\leq 10^5\)，答案取模，\(abcd\ne0\)。
操作 \(5\) 不是此题重点，可以用操作树实现，在此不赘述。
树上路径问题可以使用树链剖分或 LCT 实现。接下来仅讨论序列区间问题。
还是使用懒标记线段树。构造叶节点的矩阵：\(f_{k}=\begin{bmatrix}x_k&y_k&z_k&1\end{bmatrix}\)。（\(1\) 的设置用来辅助常数即 \(d\)，参考例题 \(1.7\)）。
那么非叶节点的矩阵就为 \(f_k=f_{lson}+f_{rson}=\begin{bmatrix}\sum x&\sum y&\sum z&r-l+1\end{bmatrix}\)。
操作 \(1\) 相当于对 \(f\) 和 \(lazy\) 乘 \(\begin{bmatrix}a&0&0&0\\b&1&0&0\\c&0&1&0\\d&0&0&1\end{bmatrix}\)。
其它操作可以类似构造，即 \(\begin{bmatrix}1&a&0&0\\0&b&0&0\\0&c&1&0\\0&d&0&1\end{bmatrix}\) 和 \(\begin{bmatrix}1&0&a&0\\0&1&b&0\\0&0&c&0\\0&0&d&1\end{bmatrix}\)。
复杂度 \(O(4^3 m\log n)\)（LCT）。
https://www.luogu.com.cn/paste/yfwxrpuw
https://www.luogu.com.cn/paste/y9rc9urr
练习题目：
- P7453 [THUSCH2017] 大魔法师
动态 DP
P4719 【模板】"动态 DP"&动态树分治
\(n\) 个节点的点权树，单点修改，求最大权独立集。
\(n,m\leq 10^5\)。
考虑没有上司的舞会的做法。
记 \(f_{k,0},f_{k,1}\) 表示只关心 \(k\) 节点的子树，\(k\) 节点选不选的方案数；
容易得到 \(f_{k,0}=\sum_{nx}\max\{f_{nx,0},f_{nx,1}\},f_{k,1}=a_{k}+\sum_{nx}f_{nx,0}\)。
为了方便修改，我们对树进行实链剖分（LCT 维护）。
记 \(g_{k,0},g_{k,1}\) 表示 \(f_{k,0},f_{k,1}\) 的递推式中，虚儿子和自身权值产生的贡献。
即 \(g_{k,0}=\sum_{nx\ne hson}\max\{f_{nx,0},f_{nx,1}\},g_{k,1}=a_{k}+\sum_{nx\ne hson}f_{nx,0}\)
则我们可以用 \((\max,+)\) 广义矩阵乘法描述转移：
\[\begin{bmatrix}f_{k, 0}\\f_{k,1}\end{bmatrix}=\begin{bmatrix}g_{k,0}&g_{k,0}\\g_{k,1}&-\infty\end{bmatrix}\times\begin{bmatrix}f_{hson,0}\\f_{hson,1}\end{bmatrix} \]注意叶节点的 \(hson\) 权值被定义为 \(M_{leaf}=\begin{bmatrix}0\\0\end{bmatrix}\)。
为什么使用竖向量？
因为要适应 Splay 中 \(lson \to k\to rson\) 的前序遍历关系。
显然在实链结构不改变的情况下，\(g\) 是不会改变的。
如何修改？（\(a_x=y\)）
令 \(F_k\) 表示 \(k\) 的辅助树上子树的矩阵积，即 \(F_{k}=F_{lson}\times \begin{bmatrix}g_{k,0}&g_{k,0}\\g_{k,1}&-\infty\end{bmatrix}\times F_{rson}\)。
如果把 \(x\) access 到根，然后旋到辅助树根，此时没有一个节点的儿子是 \(x\)，就可以之间修改 \(x\) 的 \(g\)。
所以这启发我们维护 access 过程。
access 中，需要修改实儿子。这需要向 \(g\) 中添加权值或删除权值。这对于此题的求和式是简单的。
如何查询？
把原树根旋转为辅助树的根，即可得出 DP 值为 \(F_{root}\times M_{leaf}\)。
至此我们通过 \(O(n\log n)\) 的复杂度解决此题。
https://www.luogu.com.cn/paste/h8cx9ldw
可以总结出使用动态 DP 的前提条件：
- 可以用广义矩阵乘法刻画虚儿子的贡献和实儿子的贡献。
- 在插入一个新虚儿子或删除原有的一个虚儿子时可以快速更新 \(g\)。
- 更改权值后可以快速更新 \(g\)。
注意不要把“快速”局限为 \(O(1)\)。
P3781 [SDOI2017]切树游戏
\(n\) 个节点的带权树。
操作 \(1\)：单点修改权值。
操作 \(2\)：求有多少个非空联通子树，满足树内权值异或和为 \(t\)。
\(n,m\leq 3\times 10^4,a,t\leq128,t\) 不固定。答案取模。
容易发现这是个异或卷积，故令 \(A_i=FWT(x^{a_i})\)。
令 \(One=FWT(1)\)。
先考虑朴素 dp：\(f_k\) 表示 \(k\) 的子树内，选了 \(k\) 的方案数，\(F_k\) 表示可以不选 \(k\) 的方案数。（两个都是 FWT 序列）
\[f_{k}=A_k\times \prod_{nx}(One+f_{nx}),F_{k}=f_{k}+\sum_{nx}F_{nx} \]实链剖分。
\[g_{k}=A_k\times \prod_{nx\ne hson}(One+f_{nx}),G_{k}=\sum_{nx\ne hson}F_{nx} \]用 \((+,\times)\) 的矩阵乘法刻画（\(g_{k}\times (One+f_{hson})=g_k+g_k\times f_{hson}\)）：
\[\begin{bmatrix}F_{k}\\f_{k}\\1\end{bmatrix}=\begin{bmatrix}0&g_k&g_k\\1&g_k&g_k+G_k\\0&0&1\end{bmatrix}\times \begin{bmatrix}F_{hson}\\f_{hson}\\1\end{bmatrix} \]利用动态 DP 的基本方法即可。由于模数小，可以 \(O(1)\) 实现模意义除法。
由于除法可能有 \(0\)，所以对每个节点需要记录 \(cnt_k\) 表示现在的虚儿子中有多少个为 \(0\)。
需要意识到动态 DP 的虚实儿子转化不是任意加减（乘除或其它），而是插入删除，这会带来很多良好的性质。接下来这题将会体现。
https://www.luogu.com.cn/paste/8rm5r98l
BZOJ5210 最大连通子块和
\(n\) 个节点的带权有根树。
操作 \(1\)：单点修改权值。
操作 \(2\)：求 \(x\) 的子树中最大的联通子块的点权和。
\(n,m\leq 2\times 10^5\)，点权有正有负。
\(f_k\) 表示 \(k\) 的子树内，选了 \(k\) 的最大值，\(F_k\) 表示可以不选 \(k\) 的最大值。
\[f_k=a_k+\sum_{nx}\max\{f_k,0\},F_k=\max\{0,f_k,\max_{nx}\{F_{nx}\}\} \]\[g_k=a_k+\sum_{nx\ne hson}\max\{f_k,0\},G_k=\max\{0,\max_{nx\ne hson}\{F_{nx}\}\} \]利用 \((\max,+)\) 的广义矩阵乘法：
\[\begin{bmatrix}F_k\\f_k\\0\end{bmatrix}=\begin{bmatrix}0&g_k&G_k\\-\infty&g_k&0\\-\infty&-\infty&0\end{bmatrix}\times\begin{bmatrix}F_{hson}\\f_{hson}\\0\end{bmatrix} \]利用动态 DP 的基本方法，现在的问题是：\(G\) 是 \(\max\) 形式，怎么进行更改？
利用插删虚儿子的性质，对每个节点开一个可删堆维护即可。
怎么查询子树的答案？
把 \(x\) 旋到根，只保留自身和右儿子的矩阵合并即可。
复杂度 \(O(n\log^2n)\)
https://www.luogu.com.cn/paste/boz9uo5g
练习题目：
- P5024 [NOIP2018 提高组] 保卫王国
- P8820 [CSP-S 2022] 数据传输
- P6021 洪水
谢谢观看。
标签：begin,end,矩阵,times,nx,bmatrix,DP,乘法 From： https://www.cnblogs.com/ningago/p/17472070.html