讲解了一些关于矩阵的内容

矩阵

矩阵其实是个二维数组，让数按方形排列出来就是个矩阵了，与二维数组不同矩阵上定义了许多的操作。

在代码中我们为表示一个矩阵不止需要定义一个矩阵还要存储矩阵的长和宽：

struct mat{
 int a[110][110];
 int x,y;
}

在表示时应该在方阵外套上一个方/圆括号，为方便演算我们会用一个大写字母表示它

矩阵常用有加减、数乘、乘法、转置

矩阵加减、数乘满足结合律、分配律、交换律，矩阵乘法不满足交换律

加减

要求两个矩阵尺寸相同才可做加减，做法为为让对应数相加/相减

数乘

一个矩阵乘一个数，做法为这个矩阵中每个数都跟这个数相乘

转置

沿着对角线镜像翻转不是翻转90°，可表示为小标T

矩阵乘法

奇怪的要求：

1. 矩阵乘法有顺序：$AB$ 不一定等于 $BA$
2. 左边矩阵的宽度必须等于右边矩阵高度

结果：($a,b,c$表示矩阵的长/宽)

$$(a,b)times(b,c)=(a,c)$$

结果矩阵$C$中的$i$列$j$行等于矩阵$A$中第$i$行中的每一个数分别乘上矩阵$B$中$j$列每一个数的和。

struct ma {
int n, m;
ll y[105][105];
friend ma operator*(ma a, ma b) {
ma c;
c.n = a.n;
c.m = b.m;
for (int i = 0; i < a.n; ++i)
for (int j = 0; j < b.m; ++j) {
c.y[i][j] = 0;
for (int k = 0; k < a.m; ++k) {
c.y[i][j] += a.y[i][k] * b.y[k][j] % p;
c.y[i][j] %= p;
}
}
return c;
}
};

单位矩阵

对角线上全是1，其余地方都是0的矩阵，通常表达为$E$，性质为：

$$EA=A$$

（仅当尺寸合适时）

矩阵快速幂

我们都知道斐波那契数列：

$$X_n=X_{n-1}+X_{n-2}$$

它是一个线性递推公式。线性递推公式的定义为每个项的系数为常数且各个项间均为加/减号。

考虑把线性递推公式看作：

$$X_n=sum_{i=1}^r K_iX_{n-i}$$

那么我们为了计算第$n$个时间复杂度为$O(nr)$（这里将$r$不看作常量），虽然看似很小但当$n>1e9$时就会炸掉

考虑通过矩阵操作求值：

$$begin{bmatrix} K_{n-1} \K_{n-2} \vdots \K_{n-r} \end{bmatrix}begin{bmatrix} X_{n-1}& X_{n-2}& cdots&X_{n-r} \end{bmatrix}=begin{bmatrix} X_n \end{bmatrix}$$

那么我们思考在计算完一次之后要将第二个矩阵中每个元素向后推一个并插入$X_n$再删去最后一个，时间复杂度$O(n)$。

考虑单位矩阵：

$$begin{bmatrix} K_{n-1}& 1& 0&cdots&0&0 \K_{n-2}& 0& 1&cdots&0&0 \vdots&&&ddots \K_{n-r+1}& 0& 0&cdots&1&0 \K_{n-r+1}& 0& 0&cdots&0&1 \K_{n-r}& 0& 0&cdots&0&0 \end{bmatrix}begin{bmatrix} X_{n-1}& X_{n-2}& cdots&X_{n-r} \end{bmatrix}=begin{bmatrix} X_n \X_{n-1} \vdots \X_{n-r+3} \X_{n-r+2} \X_{n-r+1} \end{bmatrix}$$

而前面讲过矩阵乘法满足结合律，我们就可以像整数快速幂一样写出矩阵快速幂$O(r^3log n)$地计算线性递推公式的第$n$项了（$r^3$是矩阵乘法的复杂度）