题目背景
矩阵快速幂
题目描述
给定 n*n 的矩阵 A，求 A^k。
输入格式
第一行两个整数 n,k
接下来 n 行，每行 n 个整数，第 i 行的第 j 的数表示 Ai,j。
输出格式
输出 A^k
共 n 行，每行 n 个数，第 i 行第 j 个数表示 (A^k)i,j，每个元素对 10^9+7 取模。
样例 #1
样例输入 #1
2 1
1 1
1 1
样例输出 #1
1 1
1 1
样例输入 #2
2 3
1 2
2 1
样例输出 #2
13 14
14 13
提示
【数据范围】
对于 100\% 的数据：1<= n <= 100，0<= k <=10^12, |Ai,j| <= 1000
1. //示例代码 C++语言 2. #include <bits/stdc++.h> 3. using namespace std; 4. typedef long long LL; 5. const int M=1e9+7; 6. struct matrix{//矩阵结构体 7. LL c[102][102]; 8. matrix(){memset(c,0,sizeof(c));}//初始化矩阵 9. }A,res; 10. LL n,k; 11. matrix operator*(matrix &a,matrix &b){//原算符重载 * 12. matrix t; 13. for(int i=1;i<=n;i++) 14. for(int j=1;j<=n;j++) 15. for(int k=1;k<=n;k++)//矩阵乘法 16. t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%M; 17. return t; 18. } 19. void quickpow(LL k){//快速幂 20. for(int i=1;i<=n;i++) res.c[i][i]=1;//初始化单位矩阵 21. while(k){ 22. if(k&1) res=res*A; 23. A=A*A; 24. k>>=1; 25. } 26. } 27. int main() 28. { 29. scanf("%lld %lld",&n,&k); 30. for(int i=1;i<=n;i++) 31. for(int j=1;j<=n;j++) cin>>A.c[i][j];//读入 32. quickpow(k);//运算 33. for(int i=1;i<=n;i++){ 34. for(int j=1;j<=n;j++) 35. cout<<res.c[i][j]<<" ";//输出结果 36. cout<<endl; 37. } 38. return 0; 39. }
1. # 示例代码 Python版 2. # 样例都没问题 提交只过两个点 没找到原因 有知道原因的大神请留言指导一下 3. import numpy as np 4. M = 10 ** 9 + 7 5. 6. n, k = map(int, input().split()) 7. a = np.zeros([n, n], dtype=int) 8. res = np.zeros([n, n], dtype=int) 9. 10. for i in range(n): 11. res[i][i] = 1 12. line = input() 13. j = 0 14. for p in line.split(): 15. a[i][j] = int(p) 16. j += 1 17. 18. while k > 0: 19. if k & 1: 20. res = np.matmul(res, a) 21. res = res % M 22. a = np.matmul(a, a) 23. a = a % M 24. k >>= 1 25. 26. for i in range(n): 27. for j in range(n): 28. print(res[i][j], end=' ') 29. print('')
