C++14(g++5.4) 解法, 执行用时: 406ms, 内存消耗: 872K, 提交时间: 2019-04-03 15:16:54

#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
#define N 65
#define p 1000000007
#define int long long
#define num(i,j) ((i-1)*8+j)
using namespace std;

inline void rd(int &X){
    X=0;int w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=w?-X:X;
}

int T;
int n,x,y;
int mx[]={-1,-2,-2,-1,1,2,2,1};
int my[]={-2,-1,1,2,2,1,-1,-2};

struct nd{int a[N][N];}t,b,s;

void build(){
    for(int x=1;x<=8;x++)
        for(int y=1;y<=8;y++)
            for(int i=0;i<8;i++){
                int tx=x+mx[i],ty=y+my[i];
                if(1<=tx and tx<=8 and 1<=ty and ty<=8)
                    s.a[num(x,y)][num(tx,ty)]=1;
            }
}
nd operator * (nd a,nd b){
    memset(t.a,0,sizeof t.a);
    for(int i=1;i<=64;i++)
        for(int j=1;j<=64;j++)
            for(int k=1;k<=64;k++)
                (t.a[i][j]+=a.a[i][k]*b.a[k][j])%=p;
    return t;
}
nd POW(nd a,int b){
    nd ans=a;b--;
    for(;b;b>>=1,a=a*a)
        if(b&1) ans=ans*a;
    return ans;
}
void work(){
    rd(n);rd(x);rd(y);
    memset(b.a,0,sizeof b.a);
    b.a[1][num(x,y)]=1;b=b*POW(s,n);
    int ans=0;
    for(int i=1;i<=64;i++)
        (ans+=b.a[1][i])%=p;
    cout<<ans<<endl;
}
signed main(){
    rd(T);build();while(T--)work();
}

C++11(clang++ 3.9) 解法, 执行用时: 158ms, 内存消耗: 620K, 提交时间: 2020-03-14 16:50:10

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const int MAX_S=65;
const int f[][2]={1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1,-2,-1};
struct Matrix
{
	LL a[MAX_S][MAX_S];
	Matrix()
	{
		memset(a,0,sizeof(a));
	}
	Matrix operator*(const Matrix &A)
	{
		Matrix B=Matrix();
		for(int k=0;k<MAX_S;++k)
		for(int i=0;i<MAX_S;++i)
		for(int j=0;j<MAX_S;++j)
		B.a[i][j]=(B.a[i][j]+a[i][k]*A.a[k][j])%MOD;
		return B;
	}
};
int n,T;
Matrix e;
void Fast_power(Matrix &res,int n);
int main()
{
	e=Matrix();
	int t=0,x,y;
	for(int i=0;i<8;++i)
	for(int j=0;j<8;++t,++j)
	for(int k=0;k<8;++k)
	{
		x=i+f[k][0];
		y=j+f[k][1];
		if(x>=0&&x<8&&y>=0&&y<8) e.a[t][x*8+y]=1;
	}
	cin>>T;
	while(T--)
	{
		cin>>n>>x>>y;
		Matrix res=Matrix();
		t=(x-1)*8+y-1;
		for(int i=0;i<MAX_S;++i)
		res.a[t][i]=e.a[t][i];
		Fast_power(res,n-1);
		LL ans=0;
		for(int i=0;i<MAX_S;++i)
		for(int j=0;j<MAX_S;++j)
		ans=(ans+res.a[i][j])%MOD;
		cout<<ans<<endl;
	}
	return 0;
}
void Fast_power(Matrix &res,int n)
{
	Matrix A=e;
	while(n)
	{
		if(n&1) res=res*A;
		A=A*A;
		n>>=1;
	}
}