poj-3233 Matrix Power(构造矩阵+矩阵快速幂)
Matrix Power Series
Time Limit: 3000MS | Memory Limit: 131072K | |
Total Submissions: 24823 | Accepted: 10304 |
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
思路:常规写无疑会超时,我们会发现S(k)=A(S(k-1))+A
所以可以构造[S(n), E]=[S(n-1), E]*[A, 0 ; A, E]=[S(1), E]*[A, 0 ; A, E]^(n-1)
用矩阵快速幂求出[A, 0 ; A, E]^(n-1)即可;
#include<cstdio>
using namespace std;
int k, n, m;
typedef struct Matrix{
int a[100][100];
}Matrix;
Matrix A, S;
Matrix mul(Matrix x, Matrix y, int row, int col)
{
Matrix c;
for(int i=1; i<=row; i++)
for(int j=1; j<=col; j++)
{
c.a[i][j]=0;
for(int k=1; k<=col; k++)
c.a[i][j]=(c.a[i][j]%m + (x.a[i][k]%m)*(y.a[k][j]%m))%m;
}
return c;
}
Matrix pow(Matrix x, int t)
{
Matrix c;
for(int i=1; i<=2*n; i++)
for(int j=1; j<=2*n; j++)
if(i==j)
c.a[i][j]=1;
else
c.a[i][j]=0;
while(t)
{
if(t&1)
{
c=mul(c, x, 2*n, 2*n);
}
x=mul(x, x, 2*n, 2*n);
t>>=1;
}
return c;
}
int main(){
scanf("%d%d%d", &n, &k, &m);
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
scanf("%d", &A.a[i][j]);
S.a[i][j]=A.a[i][j];
A.a[n+i][j]=A.a[i][j];
A.a[i][n+j]=0;
i==j? A.a[n+i][n+j]=1:A.a[n+i][n+j]=0;
i==j? S.a[i][n+j]=1:S.a[i][n+j]=0;
}
}
A=pow(A, k-1);
S=mul(S, A, n, 2*n);
for(int i=1; i<=n; i++)
{
for(int j=1; j<n; j++)
printf("%d ", S.a[i][j]);
printf("%d\n", S.a[i][n]);
}
return 0;
}
还没有评论,来说两句吧...