| Time Limit: 3000MS | Memory Limit: 131072K | |
| Total Submissions: 29541 | Accepted: 11975 |
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 1
Sample Output
1 2 2 3
Source
跟整数的分治差不多。
\[
\sum_{i=1}^kA^i=\left\{\begin{array}{}
(I+A^{k/2})\sum_{i=1}^{k/2}A^i&,&k\equiv 0\ (\bmod 2) \A+(A+A^{(k+1)/2})\sum_{i=1}^{(k-1)/2}A^i&,&k\equiv 1\ (\bmod 2)
\end{array}\right.
\]
时间复杂度\(O(n^3 \log k)\)
#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;rg char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;
co int N=30;
struct M{int a[N][N];};
int n,k,m;
M add(co M&x,co M&y){
M ans;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
ans.a[i][j]=(x.a[i][j]+y.a[i][j])%m;
return ans;
}
M mul(co M&x,co M&y){
static M ans;
memset(ans.a,0,sizeof ans.a);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
for(int k=0;k<n;++k)
ans.a[i][j]=(x.a[i][k]*y.a[k][j]%m+ans.a[i][j])%m;
return ans;
}
M ksm(M x,int k){
static M ans;
memset(ans.a,0,sizeof ans.a);
for(int i=0;i<n;++i) ans.a[i][i]=1;
for(;k;x=mul(x,x),k>>=1)
if(k&1) ans=mul(ans,x);
return ans;
}
M get(co M&x,int k){
if(k==1) return x;
M y=ksm(x,(k+1)>>1);
M z=get(x,k>>1);
return k&1?add(x,mul(add(x,y),z)):mul(add(ksm(x,0),y),z);
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
M x;
read(n),read(k),read(m);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j) x.a[i][j]=read<int>()%m;
x=get(x,k);
for(int i=0;i<n;++i,puts(""))
for(int j=0;j<n;++j) printf("%d ",x.a[i][j]);
return 0;
}原文：https://www.cnblogs.com/autoint/p/10650669.html