又是简单题。
我们知道弗洛伊德可以求解传递闭包。
我们有矩阵 \(M\)，我们给 \(M_{k,i,j}\) 定义为 \(i\to j\) 长度为 \(k\) 的路径数，细想不难发现有转移：
- \(M_{k,i,j}=\sum\limits_{p=1}^{n} (M_{k-1,i,p}\times M_{1,p,j})\)。
直接暴力弗洛伊德得到了 \(kn^3\) 的上天复杂度。
我们发现这实际就是矩阵乘法，\(M_{k}=M_{k-1}\times M_1\)。
直接矩阵乘法即可——\(M_k=M_1^k\)，结果为 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} M_{k,i,j}\)。
得到了 \(O(n^3\log k)\) 的做法。
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
long long k;
const int mod=1e9+7;
class Matrix{
public:
long long s[105][105];
void input(){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%lld",&s[i][j]);
}
void output(){
int ret=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
(ret+=s[i][j])%=mod;
}
printf("%d",ret);
}
}ans,mid,a;
Matrix operator *(const Matrix& a,const Matrix& b){
memset(mid.s,0,sizeof mid.s);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++){
mid.s[i][j]+=a.s[i][k]*b.s[k][j];
mid.s[i][j]%=mod;
}
return(mid);
}
int main(){
scanf("%d %lld",&n,&k);
a.input();
for(int i=1;i<=n;i++)ans.s[i][i]=1;
while(k>0){
if(k&1)ans=ans*a;
a=a*a;
k>>=1;
}
ans.output();
return(0);
}