http://poj.org/problem?id=3233
Matrix Power Series
| Time Limit: 3000MS | Memory Limit: 131072K | |
| Total Submissions: 18658 | Accepted: 7895 |
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
当n为奇数；假设 n = 7: A + A ^ 2 + A ^ 3 + A ^ 4 + A ^ 5 + A ^ 6 + A＾７ = A + A ^ 2 + A ^ 3 + A ^ 3 * (A + A ^ 2 + A ^ 3) + A ^ 7
当n为偶数的时候就简单了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm> using namespace std;
int n,m,k;
struct Mat
{
int mat[][];
};
Mat operator* (Mat x, Mat y)
{
Mat c;
memset(c.mat, , sizeof(c.mat));
for(int t = ; t <= n; t++)
{
for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
c.mat[i][j] = (c.mat[i][j] + x.mat[i][t] % m * (y.mat[t][j] % m) ) % m;
}
}
return c;
}
Mat operator^ (Mat x, int y)
{
Mat c;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
c.mat[i][j] = (i == j);
while(y)
{
if(y & )
c = c * x;
x = x * x;
y >>= ;
}
return c;
}
Mat operator + (Mat x, Mat y)
{
for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
x.mat[i][j] = ( x.mat[i][j] % m + y.mat[i][j] % m ) % m;
}
return x;
}
Mat dfs(int t,Mat temp)
{
if(t == )
return temp;
int mid = t / ;
Mat c = dfs(mid, temp);
if(t & )
{
c = c + (temp ^ mid ) * c;
return c + (temp ^ t); //第一次交没加括号，查了好长时间的错，惭愧惭愧，其实codeblock都waring了，弱
}
else
return c + (temp ^ mid) * c;
}
int main()
{ scanf("%d%d%d", &n,&k,&m);
Mat a,c;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
scanf("%d", &a.mat[i][j]);
c = dfs(k,a);
for(int i = ; i <= n; i++)
{
for(int j = ; j < n; j++)
printf("%d ", c.mat[i][j]);
printf("%d\n", c.mat[i][n]);
}
return ;
}