正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1111/A

---

題目大意

$2?2$的矩陣$A$，求$A^n$

---

解題思路

我們將其十進制的轉化過來，如
$$A^{2016}=(A^{10^3}{)}^2?(A^{10})?(A{)}^6$$
這樣時間復雜度為$O(lo{g}_{10}(n)?10)$

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int Size=2,XJQ=7; struct matrix{int a[Size][Size]; }f,ans; int m,l; char n[100010]; matrix operator *(matrix a,matrix b) {matrix c;memset(c.a,0,sizeof(c.a));for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)(c.a[i][j]+=a.a[i][k]*b.a[k][j]%XJQ)%=XJQ;return c; } int main() {scanf("%s",n);l=strlen(n)-1;for(int i=0;i<=l/2;i++)swap(n[i],n[l-i]);for(int i=0;i<2;i++)for(int j=0;j<2;j++)scanf("%d",&f.a[i][j]);for(int i=0;i<2;i++)ans.a[i][i]=1;for(int i=0;i<=l;i++){for(int j=1;j<=n[i]-'0';j++)ans=ans*f;f=f*f*f*f*f*f*f*f*f*f;}for(int i=0;i<2;i++){for(int j=0;j<2;j++)printf("%d ",ans.a[i][j]);putchar('\n');} }

總結

以上是生活随笔為你收集整理的牛客国庆集训派对day6T A-2016【矩阵乘法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。