題目背景
矩陣快速冪
題目描述
給定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 1 1 1 1 1
輸出樣例#1：
1 1 1 1
說明
n<=100, k<=10^12, |矩陣元素|<=1000 算法：矩陣快速冪
如題，矩陣快速冪。
已知，矩陣乘法：
第一個矩陣：
5 6 7
8 9 4
第二個矩陣：
2 3 7
2 4 8
8 3 6
相乘得：
5*2+6*2+7*8 ?5*3+6*4+7*3 ?5*7+6*8+7*6
8*2+9*2+4*8 ?8*3+9*4+4*3 ?8*7+9*8+4*6
即：
78 ?60 ?125
36 ?72 ?152
再利用快速冪可得答案。
?最后附上經我們喻隊（
PIPIBoss
）指點的代碼：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #define ll long long using namespace std; ll read() {ll x=0,y=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*y; } int n; ll k; struct ju {ll a[145][145];inline ju operator *(const ju &b)const//inline用來定義內聯函數，即在類中用的函數，可以加快速度。{ //該函數的作用是來重載*號運算符。 ju tmp;for(int i=1; i<=n; i++)for(int j=1; j<=n; j++){tmp.a[i][j]=0;for(int k=1; k<=n; k++){tmp.a[i][j]+=a[i][k]*b.a[k][j];tmp.a[i][j]%=1000000007;}}return tmp;} }ans; ju pow(ju a,ll k) {ju tmp=a;k--;while(k){if(k&1)tmp=tmp*a;a=a*a;k>>=1;}return tmp; } int main() {scanf("%d%lld",&n,&k);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)ans.a[i][j]=read();ans=pow(ans,k);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)printf("%lld ",ans.a[i][j]);putchar('\n');}return 0; }// FOR C.H.
?
最后的最后，別忘了加上頭文件，我一開始就是因為沒加頭文件錯了幾次。
