题解 | #勘测#

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;
}