矩阵快速幂
基础知识
矩阵：由$ mtimes n$个数排成的m行n列的数表
其实就是二维数组
矩阵加减法
矩阵加减法的规则：(Apm B=C)
其中$ C[i][j]$ 为(A[i][j])与(B[i][j])的和或差，即：$ C_{i j}=A_{ij}pm B_{ij}$
因此，相加减的两个矩阵$ A :B$的行列必须相同
矩阵乘法
矩阵乘法的规则：(Atimes B=C)
其中$ C[i][j]$ 为A的第i行与B的第j列对应乘积的和，即：$ C_{i j}=displaystyle sum^n_{k=1}a_{ik}* b_{kj}$
显然两个相乘是要一行和一列对应乘，那么矩阵乘法是需要A的行数与B的列数相等的，这是A*B的前提条件
这里给个例子帮助理解：
(left[ begin{matrix} a &b \c &d\e&fend{matrix} right]* left[ begin{matrix} g &h&i \j &k&lend{matrix} right]=left[ begin{matrix} ag+bj &ah+bk&ai+bl \cg+dj &ch+dk&ci+dl\eg+fj&eh+fk&ei+flend{matrix} right])
交换即是
$ left[ begin{matrix} g &h&i j &k&lend{matrix} right]*left[ begin{matrix} a &b c &de&fend{matrix} right]=left[ begin{matrix} ag+ch+ei &bg+dh+fiaj+ck+el&bj+dk+flend{matrix} right]$
可见矩阵的乘法是不满足交换律的
然后就可以发现，矩阵(C)的行数应该是(A)的行数，列数应该是(B)的列数，并且(C)也是一个方阵（行数和列数相等的矩阵）
代码：
int c[N][N];
void Mul(int a[][N],int b[][N],int n){//n是矩阵大小
memset(c,0,sizeof(c));
for(int i=1;i应用
矩阵快速幂加速递推
矩阵快速幂
矩阵幂就是算$ A^n $
根据矩阵乘法，可以发现矩阵乘法满足结合律：
证明：
上面两式子都等于
于是——
假设A是$ n*n$的矩阵，则有：
$ A = begin{cases} A, & 当m = 1时 (A^{frac m2})^2, & 当m为偶数时 (A^{frac m2})^2times A, & 当m为奇数时 end{cases}$
这个分段函数说明了矩阵快速幂的可行性，然后我们就可以得出算法：
把快速幂算法中的乘法改成矩阵的乘法就可以了
不过呢，还有一个问题，ans一开始的初始化是什么？
ans的初始化就相当于普通快速幂需要初始化为1，即乘上这个矩阵值不改变
可以发现：对于任意(2 times 2)的矩阵，乘矩阵$ left[ begin{matrix} 1 &0 & 1end{matrix} right] $值不变，因此可以设其为初始矩阵
由此可推，ans的初始化就是对角线是1其他全是0
struct node{
int z[N][N];
};
node mul(node a,node b){//矩阵乘法
node ans;
memset(ans.z,0,sizeof(ans.z));
for(int i=0;i>=1;//幂次/2
}
return ans;
}
ps：时间复杂度$ O(n^3logm)$
那么我们应该怎么加速递推呢？
先看一个简单的例子：
[POJ3070]Fibonacci
在Fibonacci整数序列中，(F_0) = 0, (F_1)=1，和(F_n) = (F_{n−1}) + (F_{n−2})(n≥2).给定整数n((0≤n≤10^9))，计算(F_n).
1.列解析式：显然：$ F(n)=F(n-1)+F(n-2)$，但这个数据范围就不是很显然了。
2.建立矩阵递推式，找到转移矩阵:
分析题目可以知道：
$F[i]=1*F[i-1]+1 *F[i-2] $
(F[i-1]=1*F[i-1]+0 *F[i-2])
将以上两个式子结合可得：
(left[ begin{matrix} F_{i-1} &F_{i-2} end{matrix} right]*left[ begin{matrix} 1 &1 \1 &0 end{matrix} right]=left[ begin{matrix} F_i &F_{i-1}end{matrix} right])
简写成$ F(n-1)*A=F(n)$，A矩阵就是那个2*2的常数矩阵
我们还可以把上述式子转换一下：
(( F[i] , F[i-1] )=( F[i-1] ,F[i-2] )*A=( F[i-2] ,F[i-3] ) *A *A)
最后可以得到：((F[n] F[n-1])=(F[1] ,F[0] )*A^{n-1})，即：(F(n)=F(1) *A^{n-1})
就愉快的转换成算矩阵快速幂了
于是——
考虑情况：$ F$是(1*n)的矩阵，$ A(是)nn(的矩阵，则)F'= FA$也是(1*n)的矩阵
(F)和(F')可以看作是一维数组，省略他们的行下标1，按照矩阵乘法的定义，有：
$ F'j=displaystylesum{k=1}^nF_k*A_{kj}$
可以认为，通过乘上矩阵(A)，从原始状态(F)递推到了(F')状态：
(left[ begin{matrix} F_1 &F_2 &F_3 end{matrix} right]times left[ begin{matrix} A_{11} &A_{12} &A_{13} \A_{21} &A_{22} &A_{23} \A_{31} &A_{32} &A_{33}end{matrix} right]=left[ begin{matrix} F'_1 &F'_2 &F'_3end{matrix} right])
那么如果假设目标状态为(G),递推矩阵为(A)，初始条件为(F)，则可得出：
(G=A^n*F)
因为我们已经会了矩阵快速幂算法，所以唯一需要我们考虑的问题就是如何构造递推矩阵(A)
再看几道题目：
Fibonacci前n项和
Fibonacci数列，f[1]=1,f[2]=1,f[n]=f[n-1]+f[n-2]，((n>2))，输入n和m，求前n项和模m的值。((1leq nleq 2times 10^{9}),(1leq mleq 1times 10^9+10))
设$ s[n](表示前) n $项和，可推出：
$s[n]=1 * s[n-1]+1* f[n]+0 f[n-1]f[n+1]=0 s[n-1]+1f[n]+1 f[n-1]f[n]=0 s[n-1]+1 f[n]+0* f[n-1] $
因此，可得矩阵：
$[ s[n] f[n+1] f[n] ]=[s[n-1] f[n] f[n-1] ]*left[ begin{matrix} 1 & 0 & 0 1 & 1 & 1 &1 & 0 end{matrix} right] $
剩下的就和上一题一样了
[POJ3734]方块涂色
N个方块排成一列 用红，蓝，绿，黄4种颜色去涂色，求红色方块 和绿色方块个数同时为偶数的 方案数 对10007取余
1.列解析式：
先定义状态分析递推式：假设已涂完前i个方块，有：
$ a[i](表示从1~i的方块中，红、绿方块数量都是偶数的方案数
)b[i](表示从1~i的方块中，红、绿方块数量一个是偶数一个是奇数的方案数
)c[i]$表示从1~i的方块中，红、绿方块数量都是奇数的方案数
初始：a(0)=1； b(0)=0； c(0)=0
分析a数组递推过程：
1.到i时红和绿的方格个数都是偶数，且i+1个方块被染成了蓝或黄色
2.到i时红和绿的方格个数一偶一奇，
且i+1个方块被染成了奇数个所对应的颜色
可得:(a[i+1]=2*a[i]+b[i])
b与c的分析如上,可得：
(b[i+1]=2*a[i]+2*b[i]+2*c[i])
(c[i+1]=b[i]+2*c[i])
2.建立矩阵递推式，找到转移矩阵:
由上可得：
$left[ begin{matrix} a_i&b_i&c_iend{matrix} right] *left[ begin{matrix} 2&2&0 1&2&1 &2& 2 end{matrix} right]=left[ begin{matrix} a_{i+1}&b_{i+1}&c_{i+1}end{matrix} right] $
矩阵快速幂加速递推题目特点：
1.可以抽象为长度为n的一维数组（即状态矩阵），矩阵在单位时间内变化一次
2.变化的形式是线性递推（只有若干”加法“或“乘以一个系数”的运算）
3.递推轮数大，但矩阵长度n不大
构建矩阵递推的大致套路：
上文常数矩阵$ A (就叫做**转移矩阵**,它能把) F[n-1] (转移到) F[n] (;然后这就是个等比数列，直接写出通项) F[n]=A^{n-1}*F[1](此处) f[1] $叫初始矩阵。
关键在于定义出状态矩阵和转移矩阵。
一般$ F[n](与)F[n-1] (都是按照原始递推式来构建的，当然可以先猜一个) F[n] $。
复杂度$ O(n^3logT)(,)T $是递归总轮数
矩阵表示修改
[THUSCH2017] 大魔法师
题目大意：n颗球，一颗球里有三个数(A) (B) (C)。有m次操作，每次操作选择一个区间([l,r])进行一下七种操作之一：
1.(A_i=A_i+B_i)
2.(B_i=B_i+C_i)
3.(C_i=C_i+A_i)
4.(A_i=A_i+v)
5.(B_i=B_itimes v)
6.(C_i=v)
7.输出(displaystylesum_{i=l}^rA_i),(displaystylesum_{i=l}^rB_i),(displaystylesum_{i=l}^rC_i)
对于区间修改，我们第一想法是线段树。但是每次修改都与该点中其他属性有关，故不能整体修改
于是就想矩阵乘法来改变状态：
把一颗球看作一个(1times 4)的矩阵([A,B,C,1])（最后一个(1)用来维护常项）
于是我们可以很轻易的推出转移矩阵：
1.([A,B,C,1]times begin{bmatrix} 1 & 0&0&0 \ 1 & 1&0&0\0&0&1&0\0&0&0&1 end{bmatrix}=[A+B,B,C,1])
2,3同理可得
4.([A,B,C,1]times begin{bmatrix} 1 & 0&0&0 \ 0 & 1&0&0\0&0&1&0\v&0&0&1 end{bmatrix}=[A+v,B,C,1])
5.([A,B,C,1]times begin{bmatrix} 1 & 0&0&0 \ 0 & v&0&0\0&0&1&0\0&0&0&1 end{bmatrix}=[A,B*v,C,1])
6.([A,B,C,1]times begin{bmatrix} 1 & 0&0&0 \ 0 & 1&0&0\0&0&0&0\0&0&v&1 end{bmatrix}=[A,B,v,1])
以第一种操作为例子，如果要修改([l,r])中的数据，那就把这段区间全部都乘一个(begin{bmatrix} 1 & 0&0&0 \ 1 & 1&0&0\0&0&1&0\0&0&0&1 end{bmatrix})就好了，于是就可以用线段树来维护了
[BZOJ2973]石头游戏
大意：有一个(n)行(m)列((0leq n,mleq 8))的矩阵，还有一个与之对应的(n)行(m)列操作序列，一共有(act)种操作序列，编号(0到（act-1）)((0leq actleq10))每一种操作序列都是长度不超过6，循环执行，一秒一个，所有格子同时进行包括：
数字0-9：拿0-9个石头到该格子
NWSE：把这个格子内所有的石头推到相邻的格子，N表示上方，W表示左方，S表示下方，E表示右方
D：拿走这个格子的石头。
问t秒((1leq tleq10^9))之后，所有方格中石头最多的格子有多少个石头
问题分析：
以样例为例，设定一维矩阵(F_t=[a_1 a_2 a_3 a_4 a_5 a_6])表示(t)秒时当前每个格子的石子数量，特别的，再加一个(a_0)，使得(a_0)始终为(1),所以,转移矩阵(T_i)第(0)列有且只有第(0)行为(1)
初始状态矩阵就是(F_0=[a_0=1 a_1=0 a_2=0 a_3=0 a_4=0 a_5=0 a_6=0])
第一秒的操作为(1,E,E,E,E,0)，第1个格子+1，第2,3,4,5个格子推向右方，第6个格子不移动不添加
所以可以构造出转移矩阵(T_1=begin{bmatrix} 1 & 1&0&0&0&0&0 \ 0 & 1&0&0&0&0&0\0&0&0&1&0&0&0\0&0&0&0&1&0&0\0&0&0&0&0&1&0\0&0&0&0&0&0&1 \0&0&0&0&0&0&1 end{bmatrix})
因此也可以通过相同的方法找到(T_2)、(T_3)、(T_4)、(T_5)...
因为(n)和(m)的数据范围较小，所以我们可以把(n)行(m)列的网络转化为长度为(ntimes m)的一维矩阵
(F_t=[a_{(1,1)},a_{(1,2)}...a_{(1,m)},a_{(2,1)}...a_{(n,m)}]),其中(a_{(i,j)})在一维矩阵第((i-1)times m+j)个位置，令(S(i,j)=(i-1)times m+j)，也再加一个$ a_0$，始终为(1)
因为每个操作序列的长度不超过(6),且(1-6)的最小公倍数为(60)，所以每经过(60)秒，操作序列又会从最开始的字符开始，因此需要构造(60)个((ntimes m+1)times (ntimes m+1))转移矩阵(T)，包含第(0-(ntimes m))行和第(0-(ntimes m))列
转移矩阵(T_i(1leq ileq 60))的构造方法：
回顾：状态矩阵(F_i)所有元素与转移矩阵(T_{i+1})第(i)列所有元素分别相乘的和，得到状态矩阵(F_{i+1})第(i)个元素的数值
注：以下操作均不计除了当前石子外，其他石子的操作对此石子的影响
若操作数字为(0-9)，设数值为(x)，所以(T_i)第(S(i,j))列 第(0)行 为(x),第(S(i,j))列 第(S(i,j))行 为(1)
若为字符(N)，则转移矩阵第(S(i,j))行 第(S(i-1,j))列为(1)，字符(W,S,E)类似
若为字符(D)，则转移矩阵此列不做处理
为了保证(F_i(0))始终为(1)，所有转移矩阵(T_i)第(0)列有且只有第(0)行为(1)
所以需要将(T_1-T_{60})全部求解出来，令(TT=T_1times T_2times ...times T_{60})
则(t)秒后：
状态矩阵(F_t=F_0*TT^{frac{t}{60}}*(T_1times T_2times ...times T_r),r=t%60)
其中(TT^{frac{t}{60}})可以用矩阵快速幂求解，最后求(F_t)中(1-(ntimes m))列的最大值即可
又可以发现一个规律：
如果在应用矩阵乘法时，遇到常数项，经常需要在“状态矩阵”中添加一个额外的位置，始终储存常数(1)，并乘上“转移矩阵”中适当的系数，累加到“状态矩阵”的其他位置
矩阵乘法与邻接矩阵
[TJOI2017]可乐
题目：
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的(1)号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第(0)秒时可乐机器人在(1)号城市，问经过了(t)秒，可乐机器人的行为方案数是多少？
(N)表示城市个数，(M)表示道路个数。
保证两座城市之间只有一条路相连，且没有任何一条道路连接两个相同的城市。
$ 1 (1≤N≤30,0
分析：
先用邻接矩阵存图（两个点之间若有边则(A[u][v]=1))
如果我们没有在原地停留和自爆两个操作，那么就是问从起点出发，走t步的不同路径数
令该图的邻接矩阵是(G),那么我们考虑 (G^2) 是个什么东西
我们单独考虑某一行和某一列的相关运算:令其为 $ G_{a,i}$和 $ G_{i,b}$令 (G′) 为相乘得到的矩阵,那么会有
$ G'{a,b}=displaystyle sum^m{i=1} G_{a,i}*G_{i,b}$
容易发现,当且仅当 $ G{a,i}$ 和 (G{i,b}) 都不为零,即(i)点可连通 (a,b) 两点的时候上式的该项才为(1), 否则为(0)
那么所有的这些情况累加起来,就是从(a)到(b)长度为(2)的路径条数(即方案数)
所以，(G^2)得到的矩阵其实表示了任意两点间长度为2的方案数
（也从(floyd)算法的角度考虑）那么不难发现(G^k)的第(i)行第(j)列的数字含义是从(i)到(j)经过(k)步的路径方案总数
那么在原地停留和自爆怎么处理？
在原地停留很简单，我们只要认为每个点都有一个从自己到自己的自环即可。
那自爆呢？
我们可以将自爆这个状态也看成一个城市，就设它为编号(0)
我们在邻接矩阵上从每个点都向这个点连一条边，这个点除了自己外不连其他出边。
这样就满足了任何一个点随时可以自爆，且无法恢复到其他状态。
最后，统计答案(Ans=sumlimits_{i=0}^{n}A[1][i])
文章来源于互联网：矩阵快速幂