Luogu 3390 【模板】矩阵快速幂 （矩阵乘法，快速幂）
Description
给定n*n的矩阵A，求A^k
第一行，n,k
第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素
Output
输出A^k
共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7
2 1 1 1 1 1
Sample Output
1 1 1 1
Http
Luogu:https://www.luogu.org/problem/show?pid=3390
Source
矩阵乘法，快速幂
解决思路
关于矩阵和矩阵乘法的内容可以到我的这一篇博客查看。 这一题需要注意的就是初始矩阵的赋值，具体请看代码。
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
const int maxN=201;
const ll Mod=1000000007;
const ll inf=2147483647;
int n;
class Matrix
{
public:
ll M[maxN][maxN];
Matrix(int x)
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
M[i][j]=x;
}
Matrix(ll Arr[maxN][maxN])
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
M[i][j]=Arr[i][j];
}
void print()
{
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
cout<<M[i][j]<<' ';
cout<<endl;
}
}
};
Matrix operator * (Matrix A,Matrix B)
{
Matrix Ans(0);
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
for (int k=0;k<n;k++)
Ans.M[i][j]=(Ans.M[i][j]+A.M[i][k]*B.M[k][j]%Mod)%Mod;
return Ans;
}
ll Arr[maxN][maxN];
ll read();
void Pow(ll Po);
int main()
{
n=read();
ll Po=read();
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
Arr[i][j]=read();
Pow(Po-1);//注意，这里为什么要-1呢，因为我们知道a^1是a，对于矩阵来说就是A^1是A,所以在传进去的时候先-1（相当于已经进行了一次操作），而若Po==1，则在Pow(Po-1)中不会执行循环，此时也正好是矩阵A（仔细揣摩一下）
return 0;
}
ll read()
{
ll x=0;
ll k=1;
char ch=getchar();
while (((ch>'9')||(ch<'0'))&&(ch!='-'))
ch=getchar();
if (ch=='-')
{
k=-1;
ch=getchar();
}
while ((ch>='0')&&(ch<='9'))
{
x=x*10+ch-48;
ch=getchar();
}
return x*k;
}
void Pow(ll P)
{
Matrix A(Arr);
Matrix B(Arr);
while (P!=0)
{
if (P&1)
A=A*B;
B=B*B;
P=P>>1;
}
A.print();
return;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7171388.html
