题目背景

矩阵快速幂

题目描述

给定n*n的矩阵A，求A^k

输入输出格式

输入格式：

第一行，n,k

第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素

输出格式：

输出A^k

共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7

输入输出样例

输入样例#1：

2 11 11 1

输出样例#1：

1 11 1

说明

n<=100, k<=10^12, |矩阵元素|<=1000 算法：矩阵快速幂

 

裸题！。

注意矩阵相乘的时候tmp的值是累加的

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define LL long long  6 using namespace std; 7 const int mod = 1e9+7; 8 LL n,k; 9 LL a[101][101];10 LL tmp[101][101];11 LL ans[101][101];12 void mul(LL a[][101],LL b[][101])13 {14     memset(tmp,0,sizeof(tmp));15     for(int i=1;i<=n;i++)16         for(int j=1;j<=n;j++)17             for(int k=1;k<=n;k++)18                 tmp[i][j]+=a[i][k]*b[k][j]%mod;19             20     for(int i=1;i<=n;i++)21         for(int j=1;j<=n;j++)22             a[i][j]=tmp[i][j]%mod; 23 }24 void fastpow(LL a[][101],LL k)25 {26     27     for(int i=1;i<=n;i++)ans[i][i]=1;28     while(k)29     {30         if(k%2)mul(ans,a);31         mul(a,a);32         k/=2;33     }34     for(int i=1;i<=n;i++)35     {36         for(int j=1;j<=n;j++)37             cout<
          
           <<" ";38         printf("\n");39     }40         41 }42 int main()43 {44     cin>>n>>k;45     for(int i=1;i<=n;i++)46         for(int j=1;j<=n;j++)47             cin>>a[i][j];48     fastpow(a,k);49     return 0;50 }