矩阵乘法 学习笔记
djwj233
2020-10-06 10:20:48
## 矩阵乘法用来做什么
可以`加速递推`。
## 矩阵乘法主过程
两个矩阵 $A$，$B$，分别为 $n\times m$，$m\times k$ 的矩阵。
设 $C=A\times B$，那么 $C$ 是 $n\times k$ 的矩阵，且:
$$C_{i,j}=\sum\limits_{k=1}^{m} A_{i,k}\times B_{k,j}$$
和 $\texttt{Floyd}$ 的转移式类似。
Code: （不带取模）
```cpp
struct mat
{
ll a[5][5];
mat(){ memset(a,0,sizeof(a)); }
mat operator*(const mat &c)const{
mat tmp;
fo(i,1,2)
fo(j,1,2)
fo(k,1,2)
tmp.a[i][j]+=a[i][k]*c.a[k][j];
return tmp;
}
};
```
单位矩阵的定义：
$$\exists f_0,\ s.t.\ \forall \textit{matrix}\ A\ ,A\times f_0=A $$
则 $f_0$ 被称为**单位矩阵**。
性质：
- 单位矩阵中的数**除向右的对角线外**都是 $0$
- 而向右的对角线上的数都是 $1$
- 如一个 $3$ 阶的单位矩阵：
$$f_0=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\\end{bmatrix}$$
## 矩阵与递推
- 设 $A_0$ 为**初始矩阵**，即在 $A_0$ 中存有初始值
- 设 $A_n$ 保存着递推 $n$ 次后的矩阵。
- 设 $f$ 为**转移矩阵**，则有 $A_0\times f^n=A_n$
如斐波那契数列中
$$\forall n\in \mathbb{N^+}\ , fib_n=\begin{cases}1&1\leq x\leq2\\
fib_{n-1}+fib_{n-2}&x\geq3\end{cases}$$
则有：
$$A_0=\begin{bmatrix}fib_1&fib_2\end{bmatrix}$$
$$A_n=\begin{bmatrix}fib_{n+1}&fib_{n+2}\end{bmatrix}$$
$$f=\begin{bmatrix}0&1\\1&1\end{bmatrix}$$
## 矩阵的设计
重点！（敲黑板）
转移矩阵**每一列**便是下一矩阵该数所对的递推式。
如上例中 $f$ 矩阵
第一列的 $\begin{bmatrix}0\\1\end{bmatrix}$ 代表
$$(A_n)_{1,1}=0\times(A_{n-1})_{1,1} +1\times (A_{n-1})_{1,2}$$
即：
$$fib_{n+1}=0\cdot fib_n+1\cdot fib_{n+1}$$
第二列的 $\begin{bmatrix}1\\1\end{bmatrix}$ 代表
$$(A_n)_{1,2}=1\times(A_{n-1})_{1,1} +1\times (A_{n-1})_{1,2}$$
即：
$$fib_{n+2}=1\cdot fib_n+1\cdot fib_{n+1}$$
## 矩阵快速幂
那么得出
$$fib_n=A_0\times f^{n-2}$$
暴力计算即可 $\Theta(n)$ 地解决此题。
好像暴力递推复杂度也一样，体现不出优势。怎么办呢？
我们发现后面这个 $f^{n-2}$ 可以快速幂，这样就可以 $\Theta(\log n)$ 地求解了。
## 模板
- [P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962)
远古代码，码风见谅
```cpp
#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fo2(v,a,b) for(v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define fe(v,a) for(int v=head[a];v;v=Next[v])
#define rg register
#define il inline
const int p=1000000007;
int a[3][3],f[3][3];long long n;//k-1,k
int c[3][3];
void mul()
{
memset(c,0,sizeof(c));
fo(i,1,2)
fo(j,1,2)
fo(k,1,2)
c[i][j]=(c[i][j]+(long long)a[i][k]*f[k][j])%p;
fo(i,1,2)
fo(j,1,2)
a[i][j]=c[i][j];
}
void mulself()
{
memset(c,0,sizeof(c));
fo(i,1,2)
fo(j,1,2)
fo(k,1,2)
c[i][j]=(c[i][j]+(long long)f[i][k]*f[k][j])%p;
fo(i,1,2)
fo(j,1,2)
f[i][j]=c[i][j];
}
int main()
{
cin>>n;
a[1][1]=a[1][2]=1;//k=2
f[1][2]=f[2][1]=f[2][2]=1;
if(n==1LL)n=0LL;
else n-=2LL;
while(n)
{
if(n&1LL)mul();
mulself();n>>=1;
}
printf("%d\n",a[1][2]);
return 0;
}
```
## 常用技巧
- [P1397 [NOI2013]矩阵游戏](https://www.luogu.com.cn/problem/P1397)
矩阵乘法依然满足
>1. 结合律
>1. 分配律
- [P6190 [NOI Online #1 入门组]魔法](https://www.luogu.com.cn/problem/P6190)
跑一遍 $\mathtt{Floyd}$ 求单次。
再将矩阵乘法中的运算**下移**：
1. $a+b$ --> $\max(a,b)$
1. $a\times b$ --> $a+b$
同时，下移后的运算也满足：
>- $\max$ 交换律
>
>- $\max$ 结合律
>- 加法交换律
>- 加法结合律
>- 加法分配律
- [P1707 刷题比赛](https://www.luogu.com.cn/problem/P1707)
码量极大，懒得写了QAQ
- [CF1182E Product Oriented Recurrence](https://www.luogu.com.cn/problem/CF1182E)
初看此题，觉得无从下手。
~~实际上想了一会儿还是无从下手~~
面对这种不按套路的乘法递推，可以采用幂的形式统计次幂数，化乘为加。
本题中，先把的次幂提出：
设 $f_n=c^{X_n}\cdot {f_1}^{a_n}{f_2}^{b_n}{f_3}^{c_n}$
那么 $\forall n\in \mathbb{N^+}\ ,$
$$X_n=\begin{cases}0&1\leq x\leq 3\\
X_{n-1}+X_{n-2}+X_{n-3}+(2n-6)&x>3\end{cases}$$
$$a_n=\begin{cases}
1&x=1\\
0&2\leq x\leq 3\\
a_{n-1}+a_{n-2}+a_{n-3}&x>3\end{cases}$$
$$b_n=\begin{cases}
1&x=2\\
0&1\leq x\leq 3\ \land x\ne 2 \\
b_{n-1}+b_{n-2}+b_{n-3}&x>3\end{cases}$$
$$c_n=\begin{cases}
1&x=3\\
0&1\leq x\leq 2\\
c_{n-1}+c_{n-2}+c_{n-3}&x>3\end{cases}$$
然后就可以矩乘了。
$a,b,c$ 设计矩阵时可以直接将前几项包含进去，然而 $X$ 不行。
怎么办呢？
可以添几个辅助项，像这样：
$$A_n=\begin{bmatrix}X_n&X_{n-1}&X_{n-2}&n&1\end{bmatrix}$$
其中 $1$ 是不变的， $n$ 是每次加一的。
每次的 $2n-6=2(n-1)-4$
则有：
$$A_0=\begin{bmatrix}0&0&0&3&1\end{bmatrix}$$
$$f=\begin{bmatrix}
1&1&0&0&0
\\1&0&1&0&0
\\1&0&0&0&0
\\2&0&0&1&0
\\-4&0&0&1&1
\end{bmatrix}$$
这样计算出 $a_n,b_n,c_n,X_n$，套用快速幂即可。
- [P3758 [TJOI2017]可乐](https://www.luogu.com.cn/problem/P3758)
图论题。
定义 $dp_{i,j}$ 为在 $i$ 时刻，目前位于 $j$ 的方案数。
设 $S(i)$ 为与 $i$ 直接相连的点的集合（包括 $i$ 自己）。
则有：
$$dp_{0,1}=1,dp_{0,x}=0\ (x\neq 1)$$
$$dp_{t,i}=\sum\limits_{j\in S(i)}dp_{t-1,j}$$
然后我们发现转移固定，可以采用矩阵优化。
一般地，在一张已确定的，$n$ 不大的图上进行 $t$ 很大的转移，可以用矩阵进行优化。
如 ：[P6772 [NOI2020]美食家](https://www.luogu.com.cn/problem/P6772)
边权不为 $1$，但很小。于是采用了拆点的形式转移。
- [P1357 花园](https://www.luogu.com.cn/problem/P1357)
有点难的状压DP，有空做。