做这个题目的时候,需要先搞定矩阵快速幂。理解起来可能相对绕一些。
1 1 sum sum + Ans*A
* =
0 A Ans Ans * A
以上矩阵的1 为单位矩阵。A为输入的矩阵
sum为全是0的矩阵
ans 为 输入的A。(因为快速幂的矩阵的1次方还是原来的矩阵。我们得不到任何答案,所以最后还是需要乘上一次A才是最后的结果)
1、此题还可以优化,一旦优化会让不会这个题目的同学造成看不懂的情况。
2、在矩阵乘法里面咱们可以遇到0,可以不用相乘。这一点可以优化。
3、主要是在二维数组的矩阵,也就是数组里面存储的是矩阵。每一个数组的元素都是一个矩阵。首先明白这个,然后其余的就好懂了。
/*****************************************
Problem Name : 矩阵快速幂求和
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e5 + 10;
int n , m;
struct node
{
int a[30][30];
node()
{
for(int i = 0 ; i < 30 ; i++)
for(int j =0 ; j < 30 ; j++)
a[i][j] = 0;
}
}p[2][2],ans[2][2]; // 定义2个矩阵,p为寻早幂次方的矩阵
node operator * (node x , node y)//运算符重栽,计算矩阵乘法
{
node c;
for(int i = 0 ; i < n ; i++)
{
for(int j =0 ; j < n ; j++)
{
for(int k = 0 ; k < n ; k++)
{
c.a[i][j] = (c.a[i][j] + x.a[i][k]*y.a[k][j])%m;
}
}
}
return c;
}
node operator + (node x , node y)//运算符重栽,计算矩阵加法
{
node c;
for(int i = 0 ; i < n ; i++)
{
for(int j =0 ; j < n ; j++)
{
c.a[i][j] = (x.a[i][j]+y.a[i][j])%m;
}
}
return c;
}
void power(int k)。// 矩阵快速幂
{
for(int i =0 ; i < n ; i++)//初始化快速幂的ans。让他变成单位矩阵。
//ans由四个矩阵组成,所以把左上角和右下角变成单位矩阵。
{
ans[0][0].a[i][i] = ans[1][1].a[i][i] = 1;
}
while(k)
{
if(k%2 == 1)// 快速幂乘法。把两个二维数组的矩阵相乘。
// ans=ans*p;
{
node t[2][2];
for(int i = 0 ; i < 2 ; i++)
{
for(int j = 0 ;j < 2 ; j++)
{
for(int k = 0 ; k < 2 ; k++)
{
t[i][j] = ( t[i][j] + ans[i][k] * p[k][j] );
}
}
}
//赋值到原先的ans
for(int i = 0 ; i < 2; i++)
for(int j = 0 ; j < 2 ; j++)
ans[i][j] = t[i][j];
}
k >>= 1;
node t[2][2];
//p = p*p;
for(int i = 0 ; i < 2 ; i++)
{
for(int j = 0 ;j < 2 ; j++)
{
for(int k = 0 ; k < 2 ; k++)
{
t[i][j] = ( t[i][j] + p[i][k] * p[k][j] );
}
}
}
//赋值到原先的p
for(int i = 0 ; i < 2; i++)
for(int j = 0 ; j < 2 ; j++)
p[i][j] = t[i][j];
}
}
void out(int x , int y) // 输出
{
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n; j++)
cout << ans[x][y].a[i][j] << " ";
cout << endl;
}
}
int main()
{
int k;
cin >> n >> k >> m;
for(int i = 0 ; i < n ; i++) // 初始化二维数组的矩阵。上面部分变成单位矩阵
p[0][1].a[i][i] =p[0][0].a[i][i] = 1;
node s; // 保留原数组。最后用上,相当于解释当中的ans
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
int x;
cin >> x;
p[1][1].a[i][j] = x;
s.a[i][j] =x;
}
}
power(k); // 调用快速幂
ans[0][1] = ans[0][1] * s; //计算最后结果
out(0,1);//结果存在二维数组矩阵ans当中的,右上角部分。
}