元素：一个个体，一般是一个数。
【向量】
向量：一组元素，向量 \(a\) 记作 \(\vec{a}\)。
我们只在乎向量的方向和大小，并不在乎向量的起点和终点。
定义： \(n\) 维向量，即 \(\vec{a}\) 中包含 \(n\) 个元素。
向量的运算：
-
向量的大小：\(|\vec{a}|\)。
-
向量加减：只有两个规模相等的向量的进行加减运算。
\(\vec{a}+\vec{b}=(a_1+b_1,a_2+b_2,\cdots,a_n+b_n)\)，减法类似。
-
向量乘以一个数：\(\vec{a}\times x\)。若 \(\vec{a}=(a_1,a_2,\cdots,a_n)\)，则 \(\vec{a} \times x = (a_1\times x, a_2\times x, \cdots, a_n\times x)\)。
-
向量乘以向量，一共两种：点乘和叉乘，这里只提点乘。
点乘只有两个向量规模相等才能进行运算。
\(\vec{a}\cdot\vec{b}=\vec{c}=(a_1 b_1,a_2b_2,\cdots,a_nb_n)\)。
【更具象化的意义】
向量：一个有方向的量。
如果没有方向，称为 “标量”；有方向，就是 “向量”。
平面向量：就是 \(2\) 维向量。
维度：如果一个向量是 \(n\) 维的，说明它可以用 \(n\) 个数确定方向。
例如 \(2\) 维向量。
\(2\) 维向量，我们在 \(2\) 维平面上研究。因为我们不在乎起点和终点，所以我们可以把起点平移到原点。
此时，终点落在平面上的一个点 \((a_1,a_2)\) 上，这就是向量的坐标。
同理，在 \(3\) 维向量中，我们可以用 \((a_1,a_2,a_3)\) 来表示终点所在的坐标。
所以，维度就是表示我们用多少个数就可以确定平面上的点。
【矩阵】
矩阵就是一些元素排成一个矩形的形式。用行和列来描述矩阵的规模。
可见，向量其实就是一种特殊的矩阵，它们的行（列）等于 \(1\)。
下面用 \(n\) 表示行数，\(m\) 表示列数。
一些关于矩阵的定义：
-
同型矩阵：两个矩阵，如果 \(n\) 和 \(m\) 对应相等，称它们为同型矩阵。
-
方阵：\(n=m\) 的矩阵。
\(a\) 阶方阵：\(n=m=a\) 的方阵。
-
对角矩阵：除了主对角线，其余所有元素都为 \(0\) 的矩阵。
主对角线上的元素都为 \(1\) 的对角矩阵，称为单位矩阵。
矩阵的运算：
-
加减，类似向量加减，规模必须相等，对应元素加减即可。
-
数乘，每个元素都乘以这个数。
-
矩阵乘法（包括向量乘以矩阵）。
如果两个矩阵 \(a,b\) 进行矩阵乘法，必须保证 \(a\) 的列数等于 \(b\) 的行数。
\[ a = \begin{pmatrix} a_{1,1}&a_{1,2}&\cdots&a_{1,m}\\ a_{2,1}&a_{2,2}&\cdots&a_{2,m}\\ \cdots&\cdots&\cdots&\cdots\\ a_{n,1}&a_{n,2}&\cdots&a_{n,m}\\ \end{pmatrix} \]\[ b = \begin{pmatrix} b_{1,1}&b_{1,2}&\cdots&b_{1,k}\\ b_{2,1}&b_{2,2}&\cdots&b_{2,k}\\ \cdots&\cdots&\cdots&\cdots\\ b_{m,1}&b_{m,2}&\cdots&b_{m,k}\\ \end{pmatrix} \]运算结果矩阵 \(c\) 是一个 \(n\times k\) 的矩阵。其中 \(c_{i,j}=\displaystyle \sum^k_{x=1}a_{i,x}\times b_{x,j}\)。
看得出来，矩阵乘法满足结合律、对矩阵加法的分配律，但是不满足交换律。
【具象化】
矩阵乘法，就是一个线性变换。
什么叫线性变换？
我们看一个函数：\(f(x)=kx\)，这是一个一次函数，也就是线性的。
类推：\(f(x_1,x_2,\cdots,x_n)=\displaystyle \sum_{i=1}^n k_ix_i\)，也是线性的。
这样我们通过 \((k_1,k_2,\cdots,k_n)\) 这个线性变换，把 \((x_1,x_2,\cdots,x_n)\) 变成了一个数。
观察矩阵乘法的运算法则：
\(c_{i,j}=\displaystyle \sum^k_{x=1}a_{i,x}\times b_{x,j}\)，这不就是可以视为线性变换吗？
把 \(a_{i,x}\) 视作上面的 \(k_i\)，\(b_{x,j}\) 视作上面的 \(x_i\)，\(c_{i,j}\) 视作线性变换的结果。
再回过头看我们的矩阵乘法：
向量乘以矩阵，得出的向量就是经过线性变换后得出的向量。
两个矩阵相乘，既可以视作很多个向量存在矩阵里，依次进行线性变换；也可以视为得出一个先做第一个变换，再做第二个变换的等价变换。
【到代码】
建议把矩阵写成一个结构体，因为在 OI 中一般只研究方阵，所以我们就只写方阵。
首先解决基本的运算，（只写矩阵乘法，因为加减法简单，向量等于矩阵）。
struct Mtr {
int n;
vector<vector<long long> > m;
Mtr (int x) {
n = x;
m = vector<vector<long long> >(n, vector<long long>(n, 0));
}
Mtr () {
n = 0;
}
void read() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> m[i][j];
}
void write() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cout << m[i][j] << ' ';
cout << endl;
}
}
} a, b;
Mtr operator*(Mtr a, Mtr b){
Mtr c = Mtr(a.n);
for (int i = 0; i < a.n; i++)
for (int j = 0; j < a.n; j++)
for (int k = 0; k < a.n; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
return c;
}
\(O(n^3)\)。
因为矩阵乘法满足结合律，所以可以考虑使用快速幂来加速运算。
（看到结合律，就要想想快速幂和线段树可不可以用。）
把矩阵包装成结构体的好处此时也显现出来了，快速幂的代码基本不用动。
看，当我们需要连续乘以一个东西的时候，我们就只能用方阵了，这也是为什么 OI 中主要研究方阵的原因。
【应用到问题】
上面的所有其实都没有真正跨入解决问题的大门。
我们说到，矩阵可以视作一个线性变换。
那么，如果我们的答案是一个经过若干次线性变换得出的，就可以考虑编成一个矩阵，然后利用快速幂在 \(\log\) 级别的时间内求出来。
例题：斐波那契数列，这题可谓相当经典。
我们看这个递推式：\(F_i=F_{i-2}+F_{i-1}\)，满足 \(y=k_1x_1+k_2x_2\) 的形式，\(F_{i-2}\rightarrow x_1,F_{i-1}\rightarrow x_2\)，这是线性变换！
所以我们可以考虑用矩阵乘法。
研究矩阵乘法的递推，我们从起点开始。
上面提到过，系数 \((k_1,\cdots,k_n)\) 是线性变换，那么 \(x_1,\cdots,x_n\) 就是起点。
所以把 \(x_1,x_2\) 存进矩阵当起点：
\[ mar = \begin{pmatrix} F_{i-2}&F_{i-1} \end{pmatrix} \]我们往后推一步：
\[ mar^{*} = \begin{pmatrix} F_{i-1}&F_{i} \end{pmatrix} \]\(mar\cdot\) 变换矩阵\(\,change\) \(=mar^{*}\)。
\(mar^{*}_{\;\;1,1}=F_{i-1}\) 正好就是 \(mar_{2,1}\)，根据矩阵乘法的定义，\(mar^*_{\;\;1,1}=mar_{1,1}change_{1,1}+mar_{1,2}change_{2,1}\)。
我们只要恰好一个 \(mar_{2,1}\)：所以\(change_{1,1}=0,change_{2,1}=1\)。
同理得：\(change_{1,2}=change_{2,2}=1\)。
所以：
\[\begin{pmatrix} F_{i-2}&F_{i-1} \end{pmatrix} \begin{pmatrix} 0&1\\ 1&1\\ \end{pmatrix} =\begin{pmatrix} F_{i-1}&F_i\\ \end{pmatrix} \]\[\begin{pmatrix} F_{1}&F_{2} \end{pmatrix} \begin{pmatrix} 0&1\\ 1&1\\ \end{pmatrix}^{i-2} =\begin{pmatrix} F_{i-1}&F_i\\ \end{pmatrix} \]同时，为了好写，我们可以把初始的一行矩阵也写成 \(2\times2\) 的方阵，第二行全是 \(0\) 即可。
【高斯消元】
高斯消元用来解决线性方程组的问题。
例如：
\[\begin{cases} 2x_1+3x_2+4x_3=20\\ x_1+2x_2+3x_3=14\\ 3x_1+x_2+2x_3=11 \end{cases} \]得出 \(x_1=1,x_2=2,x_3=3\)。
这就是线性方程组。
高斯消元法给出了一个普遍性的解决这种问题的方法。
假设我们要解决一个 \(n\) 元的线性方程组，第 \(i\) 个方程是 \(k_{i,1}x_1+k_{i,2}x_2+k_{i,3}x_3+\cdots+k_{i,n}x_n=a_i\)。
我们建立一个 \(n\times (n+1)\) 的矩阵，其中矩阵的第 \(i\) 行为 \((k_{i,1},k_{i,2},\cdots,k_{i,n},a_i)\)。
例如：
\[\begin{pmatrix} 2&3&4&20\\ 1&2&3&14\\ 3&1&2&11 \end{pmatrix} \]我们的目标是得出一个矩阵，这个矩阵左边的 \(n\times n\) 应该是一个单位矩阵。
例如：
\[\begin{pmatrix} 1&0&0&1\\ 0&1&0&2\\ 0&0&1&3\\ \end{pmatrix} \]这样，第 \(n+1\) 列的所有数就是 \(\{x_i\}\) 的解了。
回到一开始的矩阵，我们考虑考虑怎么做。
我们希望最后第一行第一列的是 \(1\)，其他行第一列的都是 \(0\)。
所以我们先让第一行第一列变成 \(1\)，也就是除一下：
\[\begin{pmatrix} 1&1.5&2&10\\ 1&2&3&14\\ 3&1&2&11 \end{pmatrix} \]然后我们用第一行 “消” 掉其他行的 \(x_1\)，这就是平时解方程的加减消元法。
\[\begin{pmatrix} 1&1.5&2&10\\ 0&0.5&1&4\\ 0&-3.5&-4&-19 \end{pmatrix} \]然后到 \(x_2\)，注意到当我们消完 \(x_1\) 的时候，对之后每一行的乘除都不会影响到第一列的系数了。
因此我们让第二行的第二列变成 \(1\)。
\[\begin{pmatrix} 1&1.5&2&10\\ 0&1&2&8\\ 0&-3.5&-4&-19 \end{pmatrix} \]这个时候再用第二行消去其他行的 \(x_2\)。因为第一列已经是 \(0\)，所以第二行加减第一行也不会影响 \(x_1\) 的系数 \(1\)。
\[\begin{pmatrix} 1&0&-1&-2\\ 0&1&2&8\\ 0&0&3&9 \end{pmatrix} \]最后到 \(x_3\)，一样的操作。
\[\begin{pmatrix} 1&0&0&1\\ 0&1&0&2\\ 0&0&1&3\\ \end{pmatrix} \]这样我们就得出了解。
但是！还有情况！无解或者无穷多解怎么办？
考虑一个无解的情况：
\(x_1+x_2=1,2x_1+2x_2=3\)
\[\begin{pmatrix} 1&1&1\\ 2&2&3 \end{pmatrix} \]消去 \(x_1\)：
\[\begin{pmatrix} 1&1&1\\ 0&0&1 \end{pmatrix} \]发现，这个时候的最后一行，前面都是 \(0\) 但是最后一列不是。
这表示 \(0\ne 0\)，矛盾，所以无解。
因此，只要我们做完高斯消元，发现有一行前面都是 \(0\) 但最后不是 \(0\)，说明无解。
再看看无穷多解。
\(x_1+x_2=1,2x_1+2x_2=2\)。
\[\begin{pmatrix} 1&1&1\\ 2&2&2 \end{pmatrix} \]消去。
\[\begin{pmatrix} 1&1&1\\ 0&0&0 \end{pmatrix} \]这个时候最后一行全都是 \(0\)，说明无穷多组解。
总结：
-
构建矩阵。
-
第 \(i\) 次操作，从 \(i\sim n\) 行中找出一个第 \(i\) 列非 \(0\) 的行，把这个行换到第 \(i\) 行的位置，用这个行消去其他行。
注意：如果找不到非 \(0\) 的行，说明无穷多组解。
-
结束后判断有没有全 \(0\) 的行或者前面全 \(0\) 但最后不是 \(0\) 的行。