正題

題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=4965

---

題目大意

給出矩陣$A,B$，求$(AB{)}^n$。然后對(duì)于每個(gè)元素$\%6$后取和。

---

題目大意

我們發(fā)現(xiàn)如果直接讓$AB?AB$這樣的時(shí)間復(fù)雜度是$n^3$，顯然不可過。但是我們注意到$k$特別小，所以我們可以將$$(AB{)}^{n?n}=A(BA{)}^{n?n?1}B$$
即可，然后時(shí)間復(fù)雜度就變?yōu)榱?span id="ze8trgl8bvbq" class="katex--inline">$O(n^{2}k+k^{3}logn)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int Size=10; struct matrix{int a[Size][Size]; }c,ans,z; int n,K,answer,B,Ans[1100][1100],a[1100][1100],b[1100][1100]; matrix operator*(matrix &a,matrix &b) {memset(z.a,0,sizeof(z.a));for(int i=0;i<Size;i++)for(int j=0;j<Size;j++)for(int k=0;k<Size;k++)(z.a[i][j]+=a.a[i][k]*b.a[k][j])%=6;return z; } int main() {while(scanf("%d%d",&n,&K)){if(n==0||K==0) return 0;B=n*n-2;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c.a,0,sizeof(c.a));memset(Ans,0,sizeof(Ans));answer=0;for(int i=0;i<n;i++)for(int j=0;j<K;j++)scanf("%d",&a[i][j]);for(int i=0;i<K;i++)for(int j=0;j<n;j++)scanf("%d",&b[i][j]);for(int i=0;i<K;i++)for(int j=0;j<K;j++)for(int k=0;k<n;k++)c.a[i][j]+=b[i][k]*a[k][j];ans=c;while(B){if(B&1) ans=ans*c;c=c*c;B>>=1;}for(int i=0;i<n;i++)for(int j=0;j<K;j++)for(int k=0;k<K;k++)Ans[i][j]+=a[i][k]*ans.a[k][j];for(int i=0;i<n;i++)for(int j=0;j<n;j++){int tmp=0;for(int k=0;k<K;k++)tmp+=Ans[i][k]*b[k][j];answer+=tmp%6;}printf("%d\n",answer);} }

總結(jié)

以上是生活随笔為你收集整理的hdu4965-Fast Matrix Calculation【矩阵乘法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。