真的是，很多时候一个小错误看不出来，一觉睡醒就好了
解题思路：因为S可以看成S=A(I+A(I+A(I+...A(I+A)))) (I是单位矩阵)
拿k=3举例S=A(I+A(I+A))
那么我们想，可不可以构造一个矩阵T使得T*T（因为是k次幂）这样乘下去每次可以得到A*(A+I)
那么肯定T有个两个元素就是A与I
那么假设：T={A I } I I 那么T=T*T={A*A+I*I A*I+I*I} A*I+I*I I*I+I*I 这样存在一个I*（A+I）的式子 ，当T再乘以T的时候会出现A（A+I）
这个时候我们可以简化将T={A I}
0 I
这样可以简化很多计算T*T={A*A A*I+I*I} 0 I
那么容易得到T^(K+1)={A^(K+1) I+A+A^2+A^3+...+A^K} //此处务必记得要减去一个但单元矩阵 0 I
这样我们只需要算T的k+1次幂就可以了
而k如此庞大所以需要二分来对T求k+1次幂
二分也就是求快速幂的方法，通过对幂指数进行二分操作，减少运算量
C - Matrix Power Series Time Limit:3000MS Memory Limit:131072KB 64bit IO Format:%lld & %llu Submit Status
Description
Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.
Input
The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.
Output
Output the elements of S modulo m in the same way as A is given.
Sample Input
2 2 4 0 1 1 1Sample Output
1 2 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include <iostream> #include <cstdio> #include <cstring> #define maxn 70 using namespace std; int m; struct matrix { int ma[maxn][maxn]; }; matrix mult(matrix a,matrix b,int cnt) { matrix ans; memset(ans.ma,0,sizeof(ans.ma)); for(int i=1;i<=cnt;i++) { for(int j=1;j<=cnt;j++) { for(int k=1;k<=cnt;k++) { ans.ma[i][j]+=(a.ma[i][k]*b.ma[k][j])%m;//此处为什么不加%m就是错的，不解 } ans.ma[i][j]=ans.ma[i][j]%m; } } return ans; } matrix pow(matrix x,int sum,int cnt) { matrix ans; memset(ans.ma,0,sizeof(ans.ma)); for(int i=1;i<=cnt;i++) { ans.ma[i][i]=1; } while(sum>0) { if(sum%2==1) { ans=mult(ans,x,cnt); } sum>>=1; x=mult(x,x,cnt); } return ans; } int main() { int n,k; matrix x,sum; scanf("%d %d %d",&n,&k,&m); memset(x.ma,0,sizeof(x.ma)); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { scanf("%d",&x.ma[i][j]); } } for(int i=1;i<=n;i++) //构造 { x.ma[i+n][i+n]=1; x.ma[i][i+n]=1; } sum=pow(x,k+1,2*n);//注意行列的变化 for(int i=1;i<=n;i++) { for(int j=n+1;j<=2*n;j++) { if(i+n==j) { printf("%d ",(sum.ma[i][j]-1+m)%m);//减去一个但单元矩阵，同时如果有因为减一而变成负数的数纠正 } else printf("%d ",sum.ma[i][j]); } printf("\n"); } return 0; }