题目背景

矩阵快速幂

题目描述

给定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 算法：矩阵快速幂

 

#include 
     
      #include 
      
       typedef long long LL;#define Mod 1000000007void read(LL &x){    x=0;    char ch=getchar();    for(;!isdigit(ch);ch=getchar());    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';}LL k,n;struct node{    LL a[150][150];    inline node operator*(const node &b)const    {        node c;        for(LL i=1;i<=n;i++)        {            for(LL j=1;j<=n;j++)            {                c.a[i][j]=0;                for(LL k=1;k<=n;k++)                c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%Mod;            }        }        return c;    }}A,ans;int main(int argc,char *argv[]){    read(n);    read(k);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            read(A.a[i][j]);    ans=A;k--;    for(;k;k>>=1LL,A=A*A)        if(k&1) ans=ans*A;    for(int i=1;i<=n;i++)    {        for(int j=1;j<=n;j++)            printf("%d ",ans.a[i][j]);        printf("\n");    }    return 0;}