题解 | #勘测#
勘测
https://ac.nowcoder.com/acm/contest/280/A
H-游戏 矩阵快速幂 考点是邻接矩阵的n次方的意义 考虑矩阵乘法的定义:
令 C=A×B C=A×B
Cij=∑k=1nAik×Bkj Cij=∑k=1nAik×Bkj
那么 A2ij=∑k=1nAik×Akj Aij2=∑k=1nAik×Akj
邻接矩阵A中的元素都是用0,1来表示是否联通的,或者说,代表有没有方法从i走到j。那么, Ai,k×AkjAi,k×Akj就是表示从i走到k再走到j是否可行。可以发现, A2A2就是取了一个 ΣΣ,其实就是统计用2步从i走到j的方法总数。 考虑累乘的效果,矩阵 (A的m)ij次方所代表的意义就是从点i到点j之间走m步能够到达的方案总数。
代码:
```#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
const int mod = 1e9+7;
int n,m;
struct M{
int a[210][210];
M(){
memset(a,0,sizeof(a));
}
M operator * (const M &b) const {
M ans;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
for(int k = 1;k<=n;k++){
ans.a[i][j] = (ans.a[i][j]%mod+(a[i][k]%mod*b.a[k][j]%mod)%mod)%mod;
}
}
}
return ans;
}
};
M Pow(M x,int y){
M ans;
for(int i = 1;i<=n;i++) ans.a[i][i] = 1;
while(y){
if(y&1) ans = ans*x;
x = x*x;
y>>=1;
}
return ans;
}
signed main(){
int t;
ios::sync_with_stdio(false);
cin.tie(0);
cin>>t>>n>>m;
M ans;
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
cin>>ans.a[i][j];
}
}
ans = Pow(ans,m);
while(t--){
int l,r;
cin>>l>>r;
cout<<ans.a[l][r]<<endl;
}
return 0;
}