https://vjudge.net/contest/182427#problem/B
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 ≤ 10^9) and m (m < 10^4). 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 1 Sample Output
1 2 2 3 Source
POJ Monthly–2007.06.03, Huang, Jinsong
如果k为偶数，那么(A+A^2+….A^K) = (A+…+A^K/2)+A^K/2*(A+…+A^K/2) 如果k为奇数，那么(A+A^2+….A^K) = (A+…+A^K/2)+A^K/2*(A+…+A^K/2)+A^k
S(k)=A+A^2+……+A^k 偶数: S(k)=S(k/2)+S(k/2)*A^(k/2) 奇数: S(k)=S(k/2)+S(k/2)*A^(k/2)+A^k;
直接用快速幂计算需要O（n）的时间，10^9的数据会超时 通过上面的公式解决超时问题
#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; int n,k,mod; struct Matrix { int a[35][35]; }; Matrix m,unit; Matrix add(Matrix x,Matrix y)//矩阵加法 { Matrix ans; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { ans.a[i][j]=0; ans.a[i][j]=(x.a[i][j]+y.a[i][j])%mod; } return ans; } Matrix multi(Matrix x,Matrix y)//矩阵乘法 { Matrix ans; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { ans.a[i][j]=0; for(int k=0; k<n; k++) ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j])%mod; } return ans; } Matrix mqmod(int l)//快速幂 { Matrix p,q; p=m,q=unit; while(l) { if(l&1)q=multi(q,p); p=multi(p,p); l>>=1; } return q; } Matrix matrixsum(int k)//利用公式递归求解 { if(k==1)return m; Matrix temp,tnow; temp=matrixsum(k/2); tnow=mqmod(k/2); temp=add(temp,multi(temp,tnow)); if(k&1)//奇数的时候多加上A^k temp=add(mqmod(k),temp); return temp; } int main() { scanf("%d%d%d",&n,&k,&mod); int q; for(int i=0; i<n; i++) for(int j=0; j<n; j++) { scanf("%d",&q); m.a[i][j]=q%mod; unit.a[i][j]=(i==j);//如果i==j那么矩阵中此值就是1,否则为0,就是主对角线是1的单位矩阵 } Matrix ans; ans=matrixsum(k); for(int i=0; i<n; i++) { for(int j=0; j<n-1; j++) printf("%d ",ans.a[i][j]); printf("%d\n",ans.a[i][n-1]); } return 0; }