矩阵

矩阵概念

row 行
column 列

单位矩阵

非对角线都是0，对角线上都是1，类似乘法中的1
一般用I表示
单位矩阵乘以任何矩阵A，都等于A本身
AI = IA = A

稀疏矩阵

三角矩阵

对称矩阵

行初等变换

交换两行
同一行自乘 k （k非0）
一行的k倍加到另一行上
主要用途是矩阵求逆

矩阵加减

矩阵乘法

矩阵转置

矩阵的逆

求矩阵A的逆
矩阵A和单位矩阵连起来组成一个n行2n列的矩阵
通过行初等变换，高斯消元，让矩阵A变成单位矩阵I
做行初等变换时，一共2n列
如果原本的矩阵A变成了单位矩阵，那么原本的单位矩阵就变成了A的逆矩阵

线性相关

矩阵的秩

行列式

特征多项式，特征方程，特征值，特征向量，

CH定理

https://en.wikipedia.org/wiki/Cayley–Hamilton_theorem

参考题目

绝大多数涉及到矩阵的题目都是矩阵乘法快速幂
少量题目利用矩阵的性质，维护前缀和或线段树

P6009 [USACO20JAN]Non-Decreasing Subsequences P

https://www.luogu.com.cn/problem/P6009

题目描述

Bessie 最近参加了一场 USACO 竞赛，遇到了以下问题。当然 Bessie 知道怎么做。那你呢？

考虑一个仅由范围在 $1 \ldots K$ （ $1 \leq K \leq 20$ ）之间的整数组成的长为 $N$ 的序列 $A_1,A_2, \ldots ,A_N$ （ $1 \leq N \leq 5 \times 10^4$ ）。给定 $Q$ （ $1 \leq Q \leq 2 \times 10^5$ ）个形式为 $[L_i,R_i]$ （ $1 \leq L_i \leq R_i \leq N$ ）的询问。对于每个询问，计算 $A_{L_i},A_{L_i+1}, \ldots ,A_{R_i}$ 中不下降子序列的数量模 $10^9+7$ 的余数。

$A_L,\ldots ,A_R$ 的一个不下降子序列是一组索引（ $j_1,j_2, \ldots ,j_x$ ），满足 $L\le j_1<j_2<\ldots<j_x\le R$ 以及 $A_{j_1}\le A_{j_2}\le \ldots \le A_{j_x}$ 。确保你考虑了空子序列！

输入格式

输入的第一行包含两个空格分隔的整数 $N$ 和 $K$ 。

第二行包含 $N$ 个空格分隔的整数 $A_1,A_2, \ldots ,A_N$ 。

第三行包含一个整数 $Q$ 。

以下 $Q$ 行每行包含两个空格分隔的整数 $L_i$ 和 $R_i$ 。

输出格式

对于每个询问 $[L_i,R_i]$ ，你应当在新的一行内输出 $A_{L_i},A_{L_i+1},\ldots, A_{R_i}$ 的不下降子序列的数量模 $10^9+7$ 的余数。

样例 #1

样例输入 #1

样例输出 #1

3
4
20

提示

样例解释

对于第一个询问，不下降子序列为 $()$ 、 $(2)$ 和 $(3)$ 。 $(2,3)$ 不是一个不下降子序列，因为 $A_2\not \le A_3$ 。

对于第二个询问，不下降子序列为 $()$ 、 $(4)$ 、 $(5)$ 和 $(4,5)$ 。

子任务

测试点 $2 \sim 3$ 满足 $N \leq 1000$ 。
测试点 $4 \sim 6$ 满足 $K \leq 5$ 。
测试点 $7 \sim 9$ 满足 $Q \leq 10^5$ 。
测试点 $10 \sim 12$ 没有额外限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x;
const int mod = 1000000007;
int p[50020][20][20], q[50020][20][20];
int f[20][20][20];
int g[20][20][20];
void amul(int a[20][20], int b[20][20], int c[20][20])
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			c[i][j] = 0;
		}
	}
	for (int i = 0; i < m; i++)
	{
		for (int k = 0; k < m; k++)
		{
			if (a[i][k] == 0)
			{
				continue;
			}
			for (int j = 0; j < m; j++)
			{
				c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
			}
		}
	}
}
void bmul(int a[20][20], int b[20][20], int c[20][20])
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			c[i][j] = 0;
		}
	}
	for (int j = 0; j < m; j++)
	{
		for (int k = 0; k < m; k++)
		{
			if (b[k][j] == 0)
			{
				continue;
			}
			for (int i = 0; i < m; i++)
			{
				c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
			}
		}
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < m; j++)
		{
			f[i][j][j] = 1;
			g[i][j][j] = 1;
		}
		for (int j = 0; j <= i; j++)
		{
			f[i][j][i] += 1;
			g[i][j][i] = (g[i][j][i] + (mod - 1) / 2) % mod;
		}
	}
	for (int i = 0; i < m; i++)
	{
		p[0][i][i] = 1;
		q[0][i][i] = 1;
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &x);
		x--;
		bmul(p[i - 1], f[x] , p[i]);
		amul(g[x] , q[i - 1], q[i]);
	}
	int t, l, r;
	scanf("%d", &t);
	for (int i = 0; i < t; i++)
	{
		scanf("%d%d", &l, &r);
		l--;
		int ans = 0;
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < m; j++)
			{
				ans = (ans + (long long)q[l][0][i] * p[r][i][j]) % mod;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

矩阵