目录
- 经典例题
- 总结
经典例题
网上有什么十大经典例题，但无非3种操作：矩阵的基础运算（例一+加减乘+阶乘），找辅助矩阵解题，与其他知识点结合用作矩阵加速（降复杂度，一般降成logn）
操作一：单单矩阵的基础操作
给定n个点，m个操作，构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转，置换
有些模拟题也会用到矩阵的基础操作，但很少这种矩阵运算。
高阶操作：反复置换，共轭转置，酉矩阵，（半）正定矩阵等等
上述定义
操作二 ：阶乘
给定矩阵A，请快速计算出A^n（n个A相乘）的结果，输出的每个数都mod p。
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
变式：用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果。
这种题本质上还是一样的，利用状态转换，画个有向图，然后跟上面的问题一样了。
例题：规定宽度为4，给定长度为n，求用12和21的瓷砖，将其完全铺满能有多少种方法。（链接一，还有杜教BM）
链接二，有推导过程
例如 ：二阶矩阵如下
const int N=2;
typedef struct matrix{ int a[N][N]; }mt;
mt muti(mt x,mt y){
mt z; memset(z.a,0,sizeof(z.a));
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
z.a[i][j]=(z.a[i][j]+x.a[i][j]*y.a[j][k]%mod)%mod;
return z;
}
mt qpow(mt x,int k){
mt y; memset(y.a,0,sizeof(y.a));
for(int i=0;i<N;i++) y.a[i][i]=1;
while(k){
if(k&1) y=muti(y,x);
k>>=1; x=muti(x,x);
}
return y;
}
一个nm的矩阵乘一个mp的矩阵会得到一个n*p的矩阵
//n*m的矩阵乘 m*p的矩阵
typedef struct matrix{ int n,m,a[maxn][maxn]; }mt;
mt muti(mt x,mt y,int n,int m,int p){
mt z; memset(z.a,0,sizeof(z.a));
for(int i=0;i<x.m;i++) //m
for(int j=0;j<y.n;j++) //p
for(int k=0;k<x.n;k++) //n
z.a[i][j]=(z.a[i][j]+x.a[i][j]*y.a[j][k]%mod)%mod;
return z;
}
操作三 ：找辅助矩阵
1、专业点说是：用矩阵乘法优化的线性齐次递推公式求值。
2、线性关系推不出的话，可以尝试杜教BM，暴力推出系数，如果推不出，应该不是线性关系。（小编还不会杜教BM）
3、这类题有时也可以用二分，dfs+剪枝，dp等等做。
题型：
1、给定n和p，求第n个Fibonacci数mod p的值，n不超过2^31
普通的有两种方法：详解
往往是变式题，要自己找辅助矩阵
对于f(n)=af(n-1)+bf(n-2)这种递推公式。有一种方法是提特征根方程：讲解
但上面的方法对于特征根是无理数时，无效，无特征根时又要考虑其是否有周期性。而用矩阵乘法写的普适性更强。
找辅助矩阵练习：
一：求Fibonacci前n项和
矩阵递推式；
Sn = 1 * Sn-1 + 1 * fn + 0 * fn-1;
fn+1 = 0 * Sn-1 + 1 * fn + 1 * fn-1;
fn = 0 * Sn-1 + 1 * fn + 0 * fn-1;
{ 1 1 0}
{ 0 1 1}
{ 0 1 0}
二：求Tn= ∑k*fk mod m；
原式
f[i] = f[i-1]+f[i-2]
T[n] = f[1]+f[2]*2+f[3]*3+...+f[n]*n
令
S[n] = f[1]+f[2]+f[3]+...+f[n]
n*S[n] = n*f[1]+n*f[2]+n*f[3]+...+n*f[n]
设
--> P[n] = n*S[n]-T[n]
--> P[n] = (n-1)*f[1]+(n-2)*f[2]+...+(n-n)*f[n]
因为
--> P[n-1] = (n-1)*S[n]-T[n-1]
--> P[n-1] = (n-2)*f[1]+(n-3)*f[2]+...+(n-1-(n-1))*f[n-1]
且
--> S[n-1] = f[1]+f[2]+f[3]+....+f[n-1]
所以
P[n]=P[n-1]+S[n-1]
P[n]=1*P[n-1]+1*S[n-1]+0*f[n]+0*f[n-1];
S[n]=0*P[n-1]+1*S[n-1]+1*f[n]+0*f[n-1];
f[n+1]=0*P[n-1]+0*S[n-1]+1*f[n]+1*f[n-1];
f[n]=0*P[n-1]+0*S[n-1]+1*f[n]+0*f[n-1];
P[i] S[i] f[i] f[i-1]
{ 1 1 0 0}
{ 0 1 1 0}
{ 0 0 1 1}
{ 0 0 1 0}
最后 T[n] = n*S[n]-P[n];
2、二分递归或找辅助矩阵
题目大意：给定矩阵A，求A + A^2 + A^3 + … + A^k的结果（两个矩阵相加就是对应位置分别相加）。输出的数据mod m。k<=10^9。
一共有4种解法，归于两大种，年代已久，链接已失（其实是懒得再找了）。
3、求下列函数的整数部分（含根号）
推导过程：矩阵快速幂+共轭复数
然后是通用公式，求整数部分
注意这类都有一个大前提才能共轭构造，见推导过程
总结
还在刷题，这篇还在更新，没什么好总结的。
