by lcx,zjy
矩陣：由$ m\times n$個數排成的m行n列的數表
其實就是二維陣列
矩陣加減法的規則：\(A\pm B=C\)
其中$ C[i][j]$ 為\(A[i][j]\)與\(B[i][j]\)的和或差，即：$ C_{i j}=A_{ij}\pm B_{ij}$
因此，相加減的兩個矩陣$ A :B$的行列必須相同
矩陣乘法的規則：\(A\times 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&f\end{matrix} \right]* \left[ \begin{matrix} g &h&i \\j &k&l\end{matrix} \right]=\left[ \begin{matrix} ag+bj &ah+bk&ai+bl \\cg+dj &ch+dk&ci+dl\\eg+fj&eh+fk&ei+fl\end{matrix} \right]\)
交換即是
$ \left[ \begin{matrix} g &h&i \j &k&l\end{matrix} \right]*\left[ \begin{matrix} a &b \c &d\e&f\end{matrix} \right]=\left[ \begin{matrix} ag+ch+ei &bg+dh+fi\aj+ck+el&bj+dk+fl\end{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<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
c[i][j]+=a[i][k]*b[k][j];
}
}
}
}
矩陣冪就是算$ A^n $
根據矩陣乘法，可以發現矩陣乘法滿足結合律：
證明：
上面兩式子都等於
於是——
假設A是$ n*n$的矩陣，則有：
$ A = \begin{cases} A, & 當m = 1時 \ (A^{\frac m2})^2, & 當m為偶數時 \ (A^{\frac m2})^2\times A, & 當m為奇數時 \end{cases}$
這個分段函數說明了矩陣快速冪的可行性，然後我們就可以得出演演算法：
把快速冪演演算法中的乘法改成矩陣的乘法就可以了
不過呢，還有一個問題，ans一開始的初始化是什麼？
ans的初始化就相當於普通快速冪需要初始化為1，即乘上這個矩陣值不改變
可以發現：對於任意\(2 \times 2\)的矩陣，乘矩陣$ \left[ \begin{matrix} 1 &0 \0 & 1\end{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<N;i++)
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
ans.z[i][j]=(ans.z[i][j]+a.z[i][k]*b.z[k][j]%mod)%mod;
return ans;
}
node power(int cnt){//快速冪，只不過底數換成了矩陣
node ans,A;
memset(ans.z,0,sizeof(ans.z));
//A一些賦值
for(int i=0;i<N;i++)ans.z[i][i]=1;//ans的賦值
while(cnt){
if(cnt&1)//奇數的話ans*A
ans=mul(ans,A);
A=mul(A,A);//A平方
cnt>>=1;//冪次/2
}
return ans;
}
ps：時間複雜度$ O(n^3logm)$
那麼我們應該怎麼加速遞推呢？
先看一個簡單的例子：
在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=\displaystyle\sum{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'_3\end{matrix} \right]\)
那麼如果假設目標狀態為\(G\),遞推矩陣為\(A\)，初始條件為\(F\)，則可得出：
\(G=A^n*F\)
因為我們已經會了矩陣快速冪演演算法，所以唯一需要我們考慮的問題就是如何構造遞推矩陣\(A\)
再看幾道題目：
Fibonacci數列，f[1]=1,f[2]=1,f[n]=f[n-1]+f[n-2]，(\(n>2\))，輸入n和m，求前n項和模m的值。(\(1\leq n\leq 2\times 10^{9}\),\(1\leq m\leq 1\times 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\0 &1 & 0 \end{matrix} \right] $
剩下的就和上一題一樣了
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_i\end{matrix} \right] *\left[ \begin{matrix} 2&2&0 \1&2&1\0 &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 $是遞迴總輪數
題目大意：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_i\times v\)
6.\(C_i=v\)
7.輸出\(\displaystyle\sum_{i=l}^rA_i\),\(\displaystyle\sum_{i=l}^rB_i\),\(\displaystyle\sum_{i=l}^rC_i\)
對於區間修改，我們第一想法是線段樹。但是每次修改都與該點中其他屬性有關，故不能整體修改
於是就想矩陣乘法來改變狀態：
把一顆球看作一個\(1\times 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}\)就好了，於是就可以用線段樹來維護了
大意：有一個\(n\)行\(m\)列\((0\leq n,m\leq 8)\)的矩陣，還有一個與之對應的\(n\)行\(m\)列操作序列，一共有\(act\)種操作序列，編號\(0到（act-1）\)\((0\leq act\leq10)\)每一種操作序列都是長度不超過6，迴圈執行，一秒一個，所有格子同時進行包括：
數位0-9：拿0-9個石頭到該格子
NWSE：把這個格子內所有的石頭推到相鄰的格子，N表示上方，W表示左方，S表示下方，E表示右方
D：拿走這個格子的石頭。
問t秒\((1\leq t\leq10^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\)列的網路轉化為長度為\(n\times 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\)個\((n\times m+1)\times (n\times m+1)\)轉移矩陣\(T\)，包含第\(0-(n\times m)\)行和第\(0-(n\times m)\)列
轉移矩陣\(T_i(1\leq i\leq 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_1\times T_2\times ...\times T_{60}\)
則\(t\)秒後：
狀態矩陣\(F_t=F_0*TT^{\frac{t}{60}}*(T_1\times T_2\times ...\times T_r),r=t\%60\)
其中\(TT^{\frac{t}{60}}\)可以用矩陣快速冪求解，最後求\(F_t\)中\(1-(n\times m)\)列的最大值即可
又可以發現一個規律：
如果在應用矩陣乘法時，遇到常數項，經常需要在「狀態矩陣」中新增一個額外的位置，始終儲存常數\(1\)，並乘上「轉移矩陣」中適當的係數，累加到「狀態矩陣」的其他位置
題目：
加里敦星球的人們特別喜歡喝可樂。因而，他們的敵對星球研發出了一個可樂機器人，並且放在了加里敦星球的\(1\)號城市上。這個可樂機器人有三種行為： 停在原地，去下一個相鄰的城市，自爆。它每一秒都會隨機觸發一種行為。現在給加里敦星球城市圖，在第\(0\)秒時可樂機器人在\(1\)號城市，問經過了\(t\)秒，可樂機器人的行為方案數是多少？
\(N\)表示城市個數，\(M\)表示道路個數。
保證兩座城市之間只有一條路相連，且沒有任何一條道路連線兩個相同的城市。
$ 1 < t \leq 10^6, $ \(1≤N≤30,0<M<100，1 \leq u, v \leq N\)
分析：
先用鄰接矩陣存圖（兩個點之間若有邊則\(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=\sum\limits_{i=0}^{n}A[1][i]\)