P3390 【模板】矩阵快速幂
本来想学动态dp 然后被一路 骗 递归 到了这里。
首先我们要知道矩阵乘法是什么，两个矩阵可以 \(A,B\) 可以相乘，当且仅当 \(A\) 的列数= \(B\)的行数
两个大小分别为 \(m \times n\) 和 \(n \times p\) 的矩阵 \(A, B\) 相乘的结果为一个大小为 \(m \times p\) 的矩阵。将结果矩阵记作 \(C\)，则
\[c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} \]其实按我的理解就是将 \(A\) 的某一行 \(i\) 整体取下来然后向下旋转 90°，然后找到第 \(j\) 列，将这两个数列 按位相乘 之后求和作为 \(C_{i,j}\) 好了我知道这很不严谨 qwq
然后我们都学过快速幂对吧，直接乘就完事了
Code:
#include<bits/stdc++.h>
#define int long long
const int N=105;
const int mod=1e9+7;
using namespace std;
int n,k;
struct Matrix{
int a[N][N];
}ANS;
Matrix operator *(const Matrix &A,const Matrix &B)
{
Matrix res={{0}};
for(int i=1;i<=n;i++)for(int k=1;k<=n;k++)for(int j=1;j<=n;j++)
{
res.a[i][j]+=A.a[i][k]*B.a[k][j];
res.a[i][j]%=mod;
}
return res;
}
Matrix qpow(Matrix x,int k)
{
Matrix K=x;
if(k<0){for(int i=1;i<=n;i++)x.a[i][i]=1;return x;}
while(k)
{
if(k&1)
{
x=x*K;
}
K=K*K;
k>>=1;
}
return x;
}
void work()
{
cin>>n>>k;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
{
scanf("%lld",&ANS.a[i][j]);
}
//cout<<n<<" "<<k<<"\n";
//return ;
if(k)
ANS=qpow(ANS,k-1);
else
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
{
cout<<(i==j ? 1 : 0)<<(j==n ? "\n" : " ");
}
return ;
}
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
{
printf("%lld",ANS.a[i][j]);
printf(j==n ? "\n" : " ");
}
}
#undef int
int main()
{
//freopen("P3390_1.in","r",stdin);freopen("P3390.out","w",stdout);
work();
return 0;
}