矩阵快速幂
和普通快速幂思路差不多
因为矩阵乘法也具有结核性
以下内容需先会快速幂,不会的出门找下面的那篇博客
void ksm(long long a[][1001],long long z){
while(z){
if (z & 1)
{
jc(ans,a);
/* code */
}
jc(a , a);
z >>= 1;
}
}
这是快速幂的模板稍微改动,把乘的那部分换成了一个函数
因为我们也是要实现幂的乘法嘛
这个函数显然不能是
return a * b
因为它要实现的是两个矩阵的乘法
矩阵的乘法公式应该都会吧
A是[n][r] B是[r][m]
c[i][j] = a[i][k] *b[k][j] + a[i][k] * b[k][j] + .... +a[i][r] * b[r][j]
也就是
(c[i][j] = sum_{k=1}^r {a[i][k]} * {b[k][j]})
(我才不会告诉你们我不会用markdown导致上面这句话打了10多分钟)
两个矩阵相乘的结果就是c矩阵
矩阵乘法的方法应该都会了
我在这里放一种普通的做法
for (long long i = 1; i <= n; ++i)
for (long long j = 1; j <= p; ++j)
for (long long k = 1; k <= m; ++k)
c[i][j] += a[i][k] * b[k][j];
完全按照定义,可以更快,但也快不了多少,一般这样写就可以
聪明的dalao们估计发现了,这就是函数的那一部分
那就加上就好啦
#include <bits/stdc++.h>
using namespace std;
long long a[1001][1001],b[1001][1001];
long long c[1001][1001],ans[1001][1001];
long long n,kd;
long long mo = 1e9 + 7;
void jc(long long a[][1001],long long b[][1001]){//把a和b乘起来
memset(c,0,sizeof c);
for (long long i = 1; i <= n; ++i)
for (long long j = 1; j <= n; ++j)
for (long long k = 1; k <= n; ++k)
c[i][j] += a[i][k] % mo * b[k][j] % mo;
for (long long i = 1; i <= n; ++i)
for (long long j = 1; j <= n; ++j){
a[i][j]=c[i][j] % mo;
}
}
void ksm(long long a[][1001],long long z){
while(z){
if (z & 1)
{
jc(ans,a);//乘出ans,就像ans *= a一样
/* code */
}
jc(a , a);//a *= a
z >>= 1;
}
}
int main()
{
freopen("testdata.in","r",stdin);
freopen("t.out","w",stdout);
cin>>n>>kd;
for (long long i = 1; i <= n; ++i)
{
for (long long j = 1; j <= n; ++j)
{
scanf("%lld",&a[i][j]);
a[i][j] %= mo;
ans[i][j] = a[i][j];
/* code */
}
/* code */
}
ksm(a,kd - 1);
for (long long i = 1; i <= n; ++i){
for (long long j = 1; j <= n; ++j)
cout<<ans[i][j] % mo<<' ';
cout<<endl;
}
return 0;
}
这其实也是洛谷p3390 矩阵快速幂的代码
由于题目要求
%了
[10^9+7
]
然后开了long long,除了这些就没什么区别了