作者：卝軎亟_621 | 来源：互联网 | 2023-05-19 18:06
Matrix Power Series
| Time Limit: 3000MS |
|
Memory Limit: 131072K |
| Total Submissions: 6040 |
|
Accepted: 2579 |
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
POJ Monthly--2007.06.03, Huang, Jinsong
#include
#include
using namespace std;
const int 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 for(int j=0;j {
res.m[i][j]=0;
for(int k=0;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 for(int j=0;j res.m[i][j]=(m1.m[i][j]+m2.m[i][j])%m;
return res;
}
Matrix power(int l)
{
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==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 {
for(int j=0;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 for(int j=0;j {
scanf("%d",&mat.m[i][j]);
mat.m[i][j]%=m;
}
print(solve(k));
return 0;
}
京公网安备 11010802041100号