Matrix Power Series
| Time Limit: 3000MS | Memory Limit: 131072K | |
| Total Submissions: 19189 | Accepted: 8099 |
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题目大意：
给定一个 n*n 的矩阵和一个整数 k,，要求的是S = A + A2 + A3 + … + Ak.
出的是 S%Mod
解题思路：
首先这是一个矩阵的快速幂，将Ak 用矩阵的快速幂求解出来（可以套模板），
可以推出以下结论
Sk = A + A2 + A3 + … + Ak
=(1+Ak/2)*(A + A2 + A3 + … + Ak/2 )+(Ak )
=(1+Ak/2)*(Sk/2 )+(Ak )
然后可以递归啦，首先计算的是 (1+ Ak/2 )，这里的 1 不仅是 1 它是一个单位矩阵，然后递归一下，最后判断一下奇偶性
要是偶数的时候就不用+(Ak )，要是奇数的话就+(Ak )，具体详见代码：
#include <iostream>
#include <cstring>
using namespace std;
typedef struct Mar
{
int m[40][40];
void Init()///初始化为单位矩阵
{
memset(m, 0, sizeof(m));
for(int i=0; i<40; i++)
m[i][i] = 1;
}
} Martrix;
int n, Mod;
Martrix Add(Martrix a, Martrix b)///矩阵加法
{
Martrix c;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
c.m[i][j] = (a.m[i][j] + b.m[i][j]) % Mod;///一定要模 Mod
return c;
}
Martrix Multi(Martrix a, Martrix b)///矩阵乘法
{
Martrix c;
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
c.m[i][j] = 0;
for(int k=0; k<n; k++)
c.m[i][j] += (a.m[i][k]*b.m[k][j])%Mod;///一定要模 Mod，将数值减小
c.m[i][j] %= Mod;
}
}
return c;
}
Martrix quick_mod(Martrix a, int b)///矩阵的快速幂
{
Martrix ans;
ans.Init();
while(b)
{
if(b & 1)
ans = Multi(ans, a);
b>>=1;///二分
a = Multi(a, a);
}
return ans;
}
Martrix Get_sum(Martrix a, int k)///递归
{
if(k == 1)
return a;
Martrix ans;
ans.Init();
ans = Add(ans, quick_mod(a, k>>1));///1+A^(k/2)
ans = Multi(ans,Get_sum(a,k>>1));///剩下的
if(k & 1)///判断奇偶性
ans = Add(ans,quick_mod(a,k));
return ans;
}
int main()
{
int k;
while(cin>>n>>k>>Mod)
{
Martrix a;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin>>a.m[i][j];
Martrix ans = Get_sum(a,k);
for(int i=0; i<n; i++)
{
for(int j=0; j<n-1; j++)
cout<<ans.m[i][j]<<" ";
cout<<ans.m[i][n-1]<<endl;
}
}
return 0;
}
