基本介紹
- 中文名：矩陣乘法
- 外文名：Matrix multiplication
- 基本性質：結合性 等
- 套用學科：數學，工程學，信息學
- 套用領域：代數，離散
定義,注意事項,基本性質,其他的乘積形式,哈達馬積（Hadamard product）,克羅內克積（Kronecker Product）,實現,實際套用,數據統計,VOJ1067,經典題目9,經典題目10,矩陣乘法例題,
定義
設A為
的矩陣，B為
的矩陣，那么稱
的矩陣C為矩陣A與B的乘積，記作
，其中矩陣C中的第
行第
列元素可以表示為：
如下所示：
注意事項
1、當矩陣A的列數（column）等於矩陣B的行數（row）時，A與B可以相乘。
2、矩陣C的行數等於矩陣A的行數，C的列數等於B的列數。
3、乘積C的第m行第n列的元素等於矩陣A的第m行的元素與矩陣B的第n列對應元素乘積之和。
基本性質
- 乘法結合律： (AB)C=A(BC)．
- 乘法左分配律：(A+B)C=AC+BC
- 乘法右分配律：C(A+B)=CA+CB
- 對數乘的結合性k(AB）=(kA)B=A(kB）．
- 轉置 (AB)T=BTAT．
- 矩陣乘法一般不滿足交換律。
其他的乘積形式
除了上述的矩陣乘法以外，還有其他一些特殊的“乘積”形式被定義在矩陣上，值得注意的是，當提及“矩陣相乘”或者“矩陣乘法”的時候，並不是指代這些特殊的乘積形式，而是定義中所描述的矩陣乘法。在描述這些特殊乘積時，使用這些運算的專用名稱和符號來避免表述歧義。
哈達馬積（Hadamard product）
克羅內克積（Kronecker Product）
實現
C++代碼
struct Matrix:vector<vector<int> >//使用標準容器vector做基類，需#include語句{ Matrix(int x=0,int y=0,int z=0)//初始化，默認為0行0列空矩陣 { assign(x,vector<int>(y,z)); } int h_size()const//常量說明不可省，否則編譯無法通過 { return size(); } int l_size()const { return empty()?0:front().size();//列數要考慮空矩陣的情況 } Matrix pow(int k);//矩陣的k次冪，用快速冪實現，k為0時返回此矩陣的單位矩陣};Matrix operator*(const Matrix &m,const Matrix &n)//常量引用避免拷貝{ if(m.l_size()!=n.h_size())return Matrix();//非法運算返回空矩陣 Matrix ans(m.h_size(),n.l_size()); for(int i=0; i!=ans.h_size(); ++i) for(int j=0; j!=ans.l_size(); ++j) for(int k=0; k!=m.l_size(); ++k) ans[i][j]+=m[i][k]*n[k][j]; return ans;}Matrix Matrix::pow(int k){ if(k==0) { Matrix ans(h_size(),h_size()); for(int i=0; i!=ans.h_size(); ++i) ans[i][i]=1; return ans; } if(k==2)return (*this)*(*this); if(k%2)return pow(k-1)*(*this); return pow(k/2).pow(2);}實際套用
數據統計
某公司有四個工廠，分布在不同地區，同時三種產品，產量（單位；t），試用矩陣統計這些數據。
| 工廠\產品 | P1 | P2 | P3 |
|---|---|---|---|
甲 | 5 | 2 | 4 |
乙 | 3 | 8 | 2 |
丙 | 6 | 0 | 4 |
丁 | 0 | 1 | 6 |
可用下述矩陣描述
，其中四行分別表示甲乙丙丁四個工廠的生產情況，三列分布表示三種產品P1，P2，P3的產量。
再設矩陣
，其中第一列表示三種產品的單件利潤，第二列表示三種產品的單件體積。
矩陣C的第一列數據分別表示四個工廠的利潤，第二列分別表示四個工廠產品需要的存儲空間。
VOJ1067
我們可以用上面的方法二分求出任何一個線性遞推式的第n項，其對應矩陣的構造方法為：在右上角的(n-1)*(n-1)的小矩陣中的主對角線上填1，矩陣第n行填對應的係數，其它地方都填0。例如，我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k項：
利用矩陣乘法求解線性遞推關係的題目有很多，這裡給出的例題是係數全為1的情況。
給定一個有向圖，問從A點恰好走k步（允許重複經過邊）到達B點的方案數mod p的值
把給定的圖轉為鄰接矩陣，即A(i,j)=1若且唯若存在一條邊i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，實際上就等於從點i到點j恰好經過2條邊的路徑數（枚舉k為中轉點）。類似地，C*A的第i行第j列就表示從i到j經過3條邊的路徑數。同理，如果要求經過k步的路徑數，我們只需要二分求出A^k即可。
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 10using namespace std;const int mod = 7777777;typedef long long LL;struct matrix{ LL a[10][10];}origin;int n,m;matrix multiply(matrix x,matrix y){ matrix temp; memset(temp.a,0,sizeof(temp.a)); for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { for (int k=0;k<n;k++) { temp.a[i][j]+=x.a[i][k]*y.a[k][j]; temp.a[i][j]=(temp.a[i][j])%mod; } } } return temp;}matrix matmod(matrix A,int k){ matrix res; memset(res.a,0,sizeof res.a); for (int i=0;i<n;i++) res.a[i][i]=1; while(k) { if (k&1) res=multiply(res,A); k>>=1; A=multiply(A,A); } return res;}void print(matrix x){ for (int i=0;i<n;i++) { for (int j=0;j<n;j++) cout<<" "<<x.a[i][j];puts(""); } printf("---------------\n");}int main(){ int k; while (cin>>n>>k) { memset(origin.a,0,sizeof origin.a); origin.a[0][0]=1; for (int i=1;i<=n;i++) { origin.a[i][0]=1; for (int j=0;j<i;j++) origin.a[i][0]+=origin.a[j][0]; } // print(origin); matrix res; memset(res.a,0,sizeof res.a); for (int i=0;i<n-1;i++) res.a[i][i+1]=1; for (int i=0;i<n;i++) res.a[n-1][i]=1; //print(res); res=matmod(res,k-1); LL fans=0; for (int i=0;i<n;i++) { fans+=res.a[0][i]*origin.a[i][0]; fans%=mod; } cout<<fans<<endl; } return 0;}經典題目9
用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M<=5，N<2^31，輸出答案mod p的結果
我們以M=3為例進行講解。假設我們把這個矩形橫著放在電腦螢幕上，從右往左一列一列地進行填充。其中前n-2列已經填滿了，第n-1列參差不齊。接下來我們要做的事情是把第n-1列也填滿，將狀態轉移到第n列上去。由於第n-1列的狀態不一樣（有8種不同的狀態），因此我們需要分情況進行討論。在圖中，我把轉移前8種不同的狀態放在左邊，轉移後8種不同的狀態放在右邊，左邊的某種狀態可以轉移到右邊的某種狀態就在它們之間連一根線。注意為了保證方案不重複，狀態轉移時我們不允許在第n-1列豎著放一個多米諾骨牌（例如左邊第2種狀態不能轉移到右邊第4種狀態），否則這將與另一種轉移前的狀態重複。把這8種狀態的轉移關係畫成一個有向圖，那么問題就變成了這樣：從狀態111出發，恰好經過n步回到這個狀態有多少種方案。比如，n=2時有3種方案，111->011->111、111->110->111和111->000->111，這與用多米諾骨牌覆蓋3x2矩形的方案一一對應。這樣這個題目就轉化為了我們前面的例題8。
後面我寫了一份此題的原始碼。你可以再次看到位運算的相關套用。
經典題目10
POJ2778
題目大意是，檢測所有可能的n位DNA串有多少個DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四個字元構成。題目將給出10個以內的病毒片段，每個片段長度不超過10。數據規模n<=2 000 000 000。
下面的講解中我們以ATC,AAA,GGC,CT這四個病毒片段為例，說明怎樣像上面的題一樣通過構圖將問題轉化為例題8。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結尾、以AA結尾、以GG結尾、以?A結尾、以?G結尾、以?C結尾和以??結尾。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。顯然，這些分類是全集的一個劃分（交集為空，並集為全集）。現在，假如我們已經知道了長度為n-1的各類DNA中符合要求的DNA個數，我們需要求出長度為n時各類DNA的個數。我們可以根據各類型間的轉移構造一個邊上帶權的有向圖。例如，從AT不能轉移到AA，從AT轉移到??有4種方法（後面加任一字母），從?A轉移到AA有1種方案（後面加個A），從?A轉移到??有2種方案（後面加G或C），從GG到??有2種方案（後面加C將構成病毒片段，不合法，只能加A和T）等等。這個圖的構造過程類似於用有限狀態自動機做串匹配。然後，我們就把這個圖轉化成矩陣，讓這個矩陣自乘n次即可。最後輸出的是從??狀態到所有其它狀態的路徑數總和。
題目中的數據規模保證前綴數不超過100，一次矩陣乘法是三方的，一共要乘log(n)次。因此這題總的複雜度是100^3 * log(n)，AC了。
最後給出第9題的代碼供大家參考（今天寫的，熟悉了一下C++的類和運算符重載）。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說：
Matrix67原創，轉貼請註明出處。
#include <cstdio>#define SIZE (1<<m)#define MAX_SIZE 32using namespace std;class CMatrix{ public: long element[MAX_SIZE][MAX_SIZE]; void setSize(int); void setModulo(int); CMatrix operator* (CMatrix); CMatrix power(int); private: int size; long modulo;};void CMatrix::setSize(int a){ for (int i=0; i<a; i++) for (int j=0; j<a; j++) element[i][j]=0; size = a;}void CMatrix::setModulo(int a){ modulo = a;}CMatrix CMatrix::operator* (CMatrix param){ CMatrix product; product.setSize(size); product.setModulo(modulo); for (int i=0; i<size; i++) for (int j=0; j<size; j++) for (int k=0; k<size; k++) { product.element[i][j]+=element[i][k]*param.element[k][j]; product.element[i][j]%=modulo; } return product;}CMatrix CMatrix::power(int exp){ CMatrix tmp=(*this)*(*this); if (exp==1) return *this; else if (exp&1) return tmp.power(exp/2)*(*this); else return tmp.power(exp/2);}int main(){ const int validSet[]={0,3,6,12,15,24,27,30}; long n, m, p; CMatrix unit; scanf("%d%d%d", &n, &m, &p); unit.setSize(SIZE); for (int i=0; i<SIZE; i++) for (int j=0; j<SIZE; j++) if (((~i)&j) == ((~i)&(SIZE-1))) { bool isValid=false; for (int k=0;k<8;k++) isValid=isValid||(i&j)==validSet[k]; unit.element[i][j]=isValid; } unit.setModulo(p); printf("%d",unit.power(n).element[SIZE-1][SIZE-1] ); return 0;}矩陣乘法例題
vijos1049
題目大意是給你一個物品變換的順序表,然後讓你求變換了n次之後物品的位置.
解析:這個題目仔細想想並不是很難,由於每一行的變換順序是不一樣的,我們需要把所給出的矩陣每一行的變換用一個矩陣乘法維護,然而如果每次都乘一下的話就很容易逾時.所以我們可以將每一行的變換得到的矩陣全部乘起來得到一個新矩陣,它就是變換k次(k是所給矩陣的行數)所乘的矩陣,那么我們就可以使用快速冪了,對於餘數就暴力算就可以啦.
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;static const int maxm=1e2+10;#define REP(i,s,t) for(int i=s;i<=t;i++) typedef long long LL;struct matrix{ LL mtx[maxm][maxm];}mx[16];LL n,k,m;LL A[maxm][maxm];matrix mul(matrix A,matrix B){ matrix ret; memset(ret.mtx,0,sizeof ret.mtx); REP(i,1,n)REP(j,1,n)REP(k,1,n) ret.mtx[i][j]=(ret.mtx[i][j]+A.mtx[i][k]*B.mtx[k][j]); return ret;}matrix pow(matrix A,LL n){ if(!n)return A; matrix ret=A;n--; while(n){ if(n&1)ret=mul(ret,A); A=mul(A,A); n>>=1; } return ret;}void display(matrix base){ for(int i=1;i<=n;i++)printf("%lld ",base.mtx[1][i]); puts("");}int main(){ matrix st,get,f; scanf("%lld%lld%lld",&n,&m,&k); for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ scanf("%lld",&A[i][j]); mx[i].mtx[A[i][j]][j]=1; } } for(int i=1;i<=n;i++)st.mtx[1][i]=i; get=mx[1]; for(int i=2;i<=m;i++)get=mul(get,mx[i]); get=pow(get,k/m);k%=m; for(int i=1;i<=k;i++)get=mul(get,mx[i]); st=mul(st,get); display(st); return 0;}//by Exbilar