Chess【矩阵快速幂】

题目大意

给你一张nxm的棋盘格，你可以在格点上下棋。
有三种选择：
op=0 棋子是车，横着走或竖着走任意步
op=1 棋子是马，走日字
op=2 棋子是象，走2x2的格子的对角
有多组数据。每一组数据给你一个选择，初始出发地点(c,d)，问你走e步后不同的路径有多少条。

范围：
nxm<=100，e<=1e9

正解

把每个格点（坐标）化成一维的，建立一个size为nm x nm的矩阵，其中的元素aij表示从i点走到j点长度为1的路径条数（三种op分开考虑）
矩阵的乘法中，如果C=AxB，那么C.a[i][j]=\(\sum_{k=1}\)A.a[i][k]*B.[k][j]
可以看成i到j需要经过一个中转点k，这样i到j的路径长度就由1变成了2.
在本题中，因此可以用矩阵快速幂求得走e步之后的矩阵（即知道了e步后任意点之间的路径条数），答案=从初始出发点对应的编号到其他所有点的路径条数之和

//chess   
//引入矩阵Mi  aij：到达aij的长度为i的路径方案数   sum（aij）：长度为i的总方案数

#include
#define ll long long
using namespace std;
const int mod = 19260817,N = 105;
ll t,n,m,c,d,e,op;
int dir_0[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dir_1[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int dir_2[4][2]={{2,-2},{2,2},{-2,2},{-2,-2}};

struct Matrix{
	int n,m;
	ll a[105][105];
	
	inline void init(int _n,int _m){
		n=_n;
		m=_m;
		memset(a,0,sizeof(a));
	} 
	
	inline void init_e(){
		for(int i=1;i<=n;i++) a[i][i]=1;
	}
	
}S;

int pos(int x,int y){
	return y+(x-1)*m;
}

Matrix mul(Matrix A,Matrix B){
		Matrix C;
		C.init(A.n,B.m);
//		puts("A");A.print();puts("");
//		puts("B");B.print();puts("");
		for(int i=1;i<=A.n;i++){
			for(int j=1;j<=B.m;j++){
				for(int k=1;k<=A.m;k++){
					C.a[i][j]=(C.a[i][j]+1ll*A.a[i][k]*B.a[k][j]%mod)%mod;
				}
			}
		}
//		puts("C");C.print();puts("");
		return C;
	}

Matrix qpow(Matrix A,ll p){
		Matrix ans; ans.init(A.m,A.m); ans.init_e();
		while(p){
			if(p%2==1) ans=mul(ans,A);
			A=mul(A,A);
			p>>=1;
		}
		return ans;
	}

void init_0(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int now=pos(i,j);
			for(int k=0;k<4;k++){
				for(int tt=1;;tt++){
					int x=i+tt*dir_0[k][0];
					int y=j+tt*dir_0[k][1];
					if(x<1||y<1||x>n||y>m) break;
					int nex=pos(x,y);
					S.a[now][nex]++;
				}
				
			}
		}
	}
}

void init_1(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int now=pos(i,j);
			for(int k=0;k<8;k++){
				int x=i+dir_1[k][0];
				int y=j+dir_1[k][1];
				if(x<1||y<1||x>n||y>m) continue;
				int nex=pos(x,y);
				S.a[now][nex]++;
			}
		}
	}
}

void init_2(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int now=pos(i,j);
			for(int k=0;k<4;k++){
				int x=i+dir_2[k][0];
				int y=j+dir_2[k][1];
				if(x<1||y<1||x>n||y>m) continue;
				int nex=pos(x,y);
				S.a[now][nex]++;
			}
		}
	}
}

int main(){
	cin>>t;
	while(t--){
		scanf("%d%d%d%d%d%d",&op,&n,&m,&c,&d,&e);
		S.init(n*m,n*m);
		if(op==0) init_0();
		if(op==1) init_1();
		if(op==2) init_2();
		
		S=qpow(S,e);
		
		int st=pos(c,d);
		ll ans=0;
		for(int i=1;i<=m*n;i++){
			ans=(ans+S.a[st][i])%mod;
		}
		printf("%lld\n",ans);
	}
	return 0;
}