C++14(g++5.4) 解法, 执行用时: 97ms, 内存消耗: 2668K, 提交时间: 2018-12-22 21:29:14

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 205;
const LL mod = 1e9+7;
LL m=0,n=0; 
struct Matrix{
  LL a[N][N];
  Matrix(){
    memset(a,0,sizeof(a));
  }
  void init(){
    for(int i=1;i<=n;++i)a[i][i]=1;
  }
  Matrix operator *(const Matrix &rhs)const{
     Matrix ret;
     for(int i=1;i<=n;++i)
      for(int j=1;j<=n;++j)
        for(int k=1;k<=n;++k)
          ret.a[i][j]=(ret.a[i][j]+a[i][k]*rhs.a[k][j]%mod)%mod;
      return ret;
  }
  Matrix operator ^(LL mi)const{
    Matrix tmp=(*this),ret;
    ret.init();
    while(mi){
      if(mi&1)ret=ret*tmp;
      tmp=tmp*tmp;
      mi>>=1;
    }
    return ret;
  }
};
int main(){
	int q=0;
	scanf("%d%lld%lld",&q,&n,&m);
	Matrix mk;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lld",&(mk.a[i][j]));
		}
	}
	Matrix ans=mk^(m);
	while(q--){
		int a1=0,b1=0;scanf("%d%d",&a1,&b1);
		printf("%lld\n",ans.a[a1][b1]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 207ms, 内存消耗: 2284K, 提交时间: 2020-03-15 13:18:10

#include<bits/stdc++.h>
using namespace std;
int x,y,n,m,Q,M=1e9+7;
struct h
{
	long long R[205][205];
	h()
	{
		memset(R,0,sizeof(R));
	}
	h operator *(const h &a)
	{
		h s;
		for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		s.R[i][j]=(s.R[i][j]+R[i][k]*a.R[k][j])%M;
		return s;
	}
}a,s;
int main()
{
	scanf("%d%d%d",&Q,&n,&m);
	for(int i=1;i<=n;i++)
	{
		s.R[i][i]=1;
		for(int j=1;j<=n;j++) scanf("%d",&a.R[i][j]);
	}
	for(;m;a=a*a,m>>=1) 
	if(m&1)
	s=s*a;
	while(Q--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",s.R[x][y]);
	}
	return 0;
}