矩阵/快速幂 学习笔记

模板及讲解

矩阵

单位矩阵:
$$
\begin{pmatrix}
1 & 0 & 0 \\\
0 & 1 & 0 \\\
0 & 0 & 1
\end{pmatrix}
$$
空矩阵:
$$
\begin{pmatrix}
0 & 0 & 0 \\\
0 & 0 & 0 \\\
0 & 0 & 0
\end{pmatrix}
$$

矩阵加法

对应位置加起来即可,矩阵加法的数初始化为空矩阵。

矩阵乘法

第一个矩阵的第$i$行的每个元素乘以第二个矩阵第$j$列的每个数的积的和就是新矩阵第$i$行$j$列的数,矩阵乘法的数初始化为单位矩阵,单位矩阵乘以任意一个矩阵是不会改变值的。

存储矩阵的时候最好用结构体,因为结构体可以直接被函数返回,而且能够较为整体化

1
2
3
4
5
6
7
8
9
10
11
12
matrix mul(matrix ai, matrix bi) {//矩阵乘法
matrix ret;
ret.init2(2, 2);
for (int i=0;i<ai.x;i++) {
for (int j=0;j<bi.y;j++) {
for (int k=0;k<ai.y;k++) {
ret.ma[i][j] = (ret.ma[i][j]%MO + (ai.ma[i][k]%MO) * (bi.ma[k][j]%MO))%MO;
}
}
}
return ret;
}

快速幂

1
2
3
4
5
6
7
8
9
int fastpow(int a,int b) { //快速幂
int ans=1,base=a;
while(b!=0){
if(b&1)ans*=base;
base*=base;
b>>=1;
}
return ans;
}

矩阵快速幂

把普通的快速幂中的乘法换为矩阵乘法即可。
矩阵快速幂求解递推方法:
构造矩阵使得
$$
\begin{pmatrix}
… \\\
… \\\

\end{pmatrix}
\times
\begin{pmatrix}
F_{n-1} \\\
F_{n-2} \\\
…\\\
F_{n-k}
\end{pmatrix}
=
\begin{pmatrix}
F_{n} \\\
F_{n-1} \\\
…\\\
F_{n-k+1}
\end{pmatrix}
$$
其中可以是$F_n = F_{n-1} + F_{n-3} + F_{n-k}$,即构造矩阵的时候可以在矩阵第一行设置$0$来消掉某个$F_i$


常见题型

1、构造矩阵优化递推
Q:求递推式$F_{n} = F_{n-1} + F_{n-3}$。
解:构造矩阵使用矩阵快速幂快速求解递推问题。
例题:AHSOFNU NOIP模拟题-2 T2
2、构造矩阵优化方案DP
Q:求递推式$F_{i,j} = F_{i-1,k}$。
解:构造矩阵使用矩阵快速幂快速求解方案DP问题。
例题:AHSOFNU NOIP模拟题-3 T3

------ 本文结束 ------