Tr A

Problem Description A為一個方陣，則Tr A表示A的跡（就是主對角線上各項的和），現要求Tr(A^k)%9973。 Input 數據的第一行是一個T，表示有T組數據。
每組數據的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)兩個數據。接下來有n行，每行有n個數據，每個數據的范圍是[0,9]，表示方陣A的內容。 Output 對應每組數據，輸出Tr(A^k)%9973。 Sample Input 2 2 2 1 0 0 1 3 99999999 1 2 3 4 5 6 7 8 9 ? ? ?output 2 2686 題意：得出一個n*n的矩陣的k次冪的矩陣，然后主對角線上的數值相加，對9973取余
注：（a+b+c+d.....+n)%mod=((((((a%mod)+b)%mod)+c)%mod)...+n)%mod;
#include <iostream> #include <string.h> using namespace std; int n,k; int MOD=9973; struct matrix {long long a[11][11]; }; matrix matrix_mul(matrix aa,matrix bb) {matrix s;memset(s.a,0,sizeof(s.a));for(int i=0;i<n;++i)for(int j=0;j<n;++j)for(int k=0;k<n;++k)if(aa.a[i][k]&&bb.a[k][j])s.a[i][j]=(s.a[i][j]+aa.a[i][k]*bb.a[k][j])%MOD;/*for(int k=0;k<n;++k)for(int i=0;i<n;++i)if(aa.a[i][k])for(int j=0;j<n;++j)if(bb.a[k][j])s.a[i][j]=(s.a[i][j]+aa.a[i][k]*bb.a[k][j])%MOD;//復雜度優化，不過還沒理解*/return s; } matrix matrix_pow(matrix a1) {if(k==0)//題目中k>=2可以不用考慮return a1;matrix e;//定義一個單位矩陣（任何矩陣乘以單位矩陣都是他的本身）memset(e.a,0,sizeof(e.a));//for(int i=0;i<n;++i)e.a[i][i]=1;//上面都是單位矩陣的的數值定義while(k)//快速冪運算{if(k&1)//冪指數為奇數的時候執行e=matrix_mul(e,a1);a1=matrix_mul(a1,a1);//使其本身平方k>>=1;//表示指數左移一位，即指數除以二}return e; } int main() {int t;cin>>t;while(t--){matrix a1,s;cin>>n>>k;for(int i=0;i<n;++i)for(int j=0;j<n;++j)cin>>a1.a[i][j];s=matrix_pow(a1);long long sum=0;for(int i=0;i<n;++i)sum=(sum+s.a[i][i])%MOD;//sum+=s.a[i][i]%MOD是sum=sum+s.a[i][i]%MOD)計算對角線上的值cout<<sum<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的HDU (1575)Tr A ---矩阵快速幂的全部內容，希望文章能夠幫你解決所遇到的問題。

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