本文介绍了一种高效计算矩阵A的幂级数求和的方法，即求从A到Ak的矩阵序列之和。通过快速幂算法优化计算过程，特别适用于大指数情况。文章提供了完整的C++代码实现。
| Time Limit: 3000MS | Memory Limit: 131072K | |
| Total Submissions: 5442 | Accepted: 2322 |
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
#include<cstdio>
#define maxn 32
int m,n,k;
struct Matrix
{
int m[maxn][maxn];
} mat;
Matrix operator * (const Matrix & m1,const Matrix & m2)
{
Matrix res;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
res.m[i][j]=0;
for(int k=0;k<n;k++)
{
res.m[i][j]+=m1.m[i][k]*m2.m[k][j];
}
res.m[i][j]%=m;
}
return res;
}
Matrix operator +(const Matrix & m1,const Matrix & m2)
{
Matrix res;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
res.m[i][j]=(m1.m[i][j]+m2.m[i][j])%m;
return res;
}
Matrix power(int l)
{
if(l<=0)
{
Matrix res;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
res.m[i][j]=0;
res.m[i][i]=1;
}
}
else if(l==1)
{
return mat;
}
else
{
Matrix res;
Matrix tmp=power(l/2);
res=tmp*tmp;
if(l&1)
res=res*mat;
return res;
}
}
Matrix solve(int k)
{
Matrix res;
if(k<=0)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
res.m[i][j]=0;
res.m[i][i]=1;
}
return res;
}
else if(k==1)
return mat;
else
{
res=solve(k/2);
if(k&1) //k是奇数
{
Matrix tmp=power(k/2+1);
res=tmp*res+res+tmp;
}
else //k是偶数
{
res=power(k/2)*res+res;
}
return res;
}
}
void print(const Matrix & m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
printf("%d ",m.m[i][j]);
printf("%d/n",m.m[i][n-1]);
}
}
int main()
{
scanf("%d%d%d",&n,&k,&m);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
scanf("%d",&mat.m[i][j]);
mat.m[i][j]%=m;
}
print(solve(k));
return 0;
}
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
