目錄
- 經典例題
- 總結
經典例題
網上有什么十大經典例題，但無非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、求下列函式的整數部分（含根號）
推導程序：矩陣快速冪+共軛復數
然后是通用公式，求整數部分
注意這類都有一個大前提才能共軛構造，見推導程序
總結
還在刷題，這篇還在更新，沒什么好總結的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/142810.html
標籤：其他