矩阵乘法与动态 DP 入门

· · 个人记录

矩阵乘法及广义矩阵乘法

前置知识：矩阵相关基础概念。 记 A(i, j) 表示矩阵 A 的第 i 行第 j 列， n_A 为 A 的行数， m_A 为 A 的列数。 定义矩阵加法 A+B 为（ n_A=n_B,m_A=m_B）：

\ \ \ \ \ [A+B](i,j)=A(i,j)+B(i,j)

矩阵加法有交换律，结合律。 定义矩阵乘法 A\times B 为（ m_A=n_B）：

\ \ \ \ \ [A\times B](i,j)=\sum_{k=1}^{m_A}(A_{i,k}\times B_{k,j})

矩阵乘法满足结合律，对矩阵加法的分配律，但不满足交换律。 定义关于运算 (\oplus, \otimes) 广义矩阵乘法 A\times B 为（ m_A=n_B）：

\ \ \ \ \ [A\times B](i,j)=\bigoplus_{k=1}^{m_A}(A_{i,k}\otimes B_{k,j})

若其存在结合律，则：

\ \ \ \ \ \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}

若：

\ \ \ \ \ \begin{aligned} \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}\bigoplus_{p=1}^{m_B}(A(i,k)\otimes B(k,p)\otimes C(p,j)) \\ \bigoplus_{k=1}^{m_B}\bigoplus_{p=1}^{m_A}(A(i,p)\otimes B(p,k)\otimes C(k,j)) & =\bigoplus_{p=1}^{m_B}\bigoplus_{k=1}^{m_A}(A(i,k)\otimes B(k,p)\otimes C(p,j)) \end{aligned}

即满足结合律。 常见的 (\oplus, \otimes) 组合有： (+,\times) ， (\max, +)。

练习题目：

矩阵递推

矩阵可以有效地解决线性组合问题。

斐波那契问题：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

总结：矩阵递推可以做的有：

其中 \Delta 需恒定。以上空位的消耗会有重叠。

练习题目：

运用矩阵解决线性组合问题

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？（原创题，可提交，不卡常（？））

操作 $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

练习题目：

动态 DP

P4719 【模板】"动态 DP"&动态树分治

$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 的前提条件：

注意不要把“快速”局限为 O(1)。

P3781 [SDOI2017]切树游戏

操作 $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 最大连通子块和

操作 $1$：单点修改权值。 操作 $2$：求 $x$ 的子树中最大的联通子块的点权和。 $n,m\leq 2\times 10^5$，点权有正有负。
$$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

练习题目：

谢谢观看。