象棋（高斯消元）

题目传送门

引

高斯消元思维题

解法

1.

对于从点$(i,j)$走出棋盘，我们发现结束的状态十分的多，不妨换个思路：

从棋盘外走到点$(i,j)$.

那么我们可以设计$DP$:
$$f_{i,j}:走到点（i，j）的期望经过回合$$
那么所有在棋盘外的$f_{i,j}=0$
设 { d x i , d y i } \{dx_i,dy_i\} {dxi​,dyi​}为一个方向的偏移，一共有$8$种,令它们的下标从$0$开始
那么就写出转移：
$$f_{i,j}=\sum _{k=0}^{k<8}{p}_k\ast f_{i+d{x}_k,j+d{y}_k}$$

2.

然后发现转移有环，不可直接转移，要用高斯消元求解
稍微计算一下复杂度：
一共有$nm$个未知量，即$nm$个方程，所以是$O((nm{)}^3)$
写好一点的话可以拿$60pts$，对于$T4$来说已经不错了

3.

考虑优化高斯消元
一个经典的想法就是设主元，减少方程数
而发现确实如此，我们知道：
$$f_{i,j}=\sum _{k=0}^{k<8}{p}_k\ast f_{i+d{x}_k,j+d{y}_k}$$
那么就有：
f i + d x 0 , j + d y 0 = f i , j ∑ k = 0 ( k < 8 ) ∧ ( k ≠ 0 ) p k ∗ f i + d x k , j + d y k p 0 f i + d x 1 , j + d y 1 = f i , j ∑ k = 0 ( k < 8 ) ∧ ( k ≠ 1 ) p k ∗ f i + d x k , j + d y k p 1 . . . . . .

​fi+dx0​,j+dy0​​=p0​fi,j​∑k=0(k<8)∧(k=0)​pk​∗fi+dxk​,j+dyk​​​fi+dx1​,j+dy1​​=p1​fi,j​∑k=0(k<8)∧(k=1)​pk​∗fi+dxk​,j+dyk​​​......​
我们就根据其构造新的方程组即可
最后回代系数算出真实结果即可

code

#include
using namespace std;
typedef long long ll;
const int dx[]={2,1,-1,-2,-2,-1,1,2};
const int dy[]={1,2,2,1,-1,-2,-2,-1};
const int N=600,mod=998244353,M=2e2+7;
int a[N][N],c[N],ans[M*M],down[N];
int ljh[M][M][N];
int cnt,cnt1,n,m,sum;
int w[17],invw[17];
int qpow(int a,int b){
	int res=1; while(b){
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod,b>>=1;
	}
	return res;
}
int gett(int x,int y) { return (x-1)*m+y;}
int inv(int x){ return qpow(x,mod-2); }
bool check(int x,int y){ return (x>=1&&x<=n&&y>=1&&y<=m);}
void Gauss(int n){
	for(int i=1;i<=n;i++) {
		int k=0;
		for(int j=i;j<=n;j++) {
			if(a[j][i]) {k=j;break;}        
		}    
		if(!k) return ;
		for(int j=1;j<=n+1;j++) swap(a[i][j],a[k][j]);        
		int p=inv(a[i][i]);
		for(int j=i;j<=n+1;j++) a[i][j]=1ll*a[i][j]*p%mod;
		for(int j=1;j<=n;j++) {
			if(j==i) continue;  
			int tmp=a[j][i];
			for(int k=1;k<=n+1;k++) {
				a[j][k]-=1ll*a[i][k]*tmp%mod;;
				a[j][k]=(a[j][k]%mod+mod)%mod;          
			}        
		}    
	}
}
void work() {
	for(int i=1;i<=m;i++) {
		ljh[1][i][++cnt]=1,down[cnt]=gett(1,i);
		ljh[2][i][++cnt]=1,down[cnt]=gett(2,i);
	}
	for(int i=3;i<=n;i++) ljh[i][1][++cnt]=1,down[cnt]=gett(i,1);    
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(check(i+2,j+1)) {
				for(int t=1;t<=cnt+1;t++) ljh[i+2][j+1][t]=ljh[i][j][t];                
				for(int k=0;k<8;k++) {
					int nx=i-dx[k],ny=j-dy[k];
					if((k==4)||(!check(nx,ny))) continue;      
					for(int t=1;t<=cnt+1;t++){              
						ljh[i+2][j+1][t]-=1ll*ljh[nx][ny][t]*w[k]%mod;
						ljh[i+2][j+1][t]=(ljh[i+2][j+1][t]%mod+mod);
					}                
				}
				ljh[i+2][j+1][cnt+1]--;
				ljh[i+2][j+1][cnt+1]=(ljh[i+2][j+1][cnt+1]%mod+mod);
				for(int t=1;t<=cnt+1;t++) 
					ljh[i+2][j+1][t]=1ll*ljh[i+2][j+1][t]*invw[4]%mod;               
			}else {
				cnt1++;
				for(int t=1;t<=cnt+1;t++) a[cnt1][t]=ljh[i][j][t];
				for(int k=0;k<8;k++) {
					int nx=i-dx[k],ny=j-dy[k];
					if((k==4)||(!check(nx,ny))) continue;                    
					for(int t=1;t<=cnt+1;t++){   
						a[cnt1][t]-=1l*ljh[nx][ny][t]*w[k]%mod;
						a[cnt1][t]=(a[cnt1][t]%mod+mod)%mod;
					}                
				}
				a[cnt1][cnt+1]--;
				a[cnt1][cnt+1]=(a[cnt1][cnt+1]%mod+mod)%mod;
				a[cnt1][cnt+1]=-a[cnt1][cnt+1];
				a[cnt1][cnt+1]=(a[cnt1][cnt+1]%mod+mod)%mod;
			}        
		}    
	}
	Gauss(cnt);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			for(int t=1;t<=cnt;t++) 
				ans[gett(i,j)]=(1ll*ans[gett(i,j)]+1ll*a[t][cnt+1]*ljh[i][j][t]%mod)%mod;
			ans[gett(i,j)]=(1ll*ans[gett(i,j)]+1ll*ljh[i][j][cnt+1])%mod; 
		}    
	}
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<8;i++) {
		scanf("%d",&w[i]);
		sum+=w[i];
	}
	sum=inv(sum);
	for(int i=0;i<8;i++) {
		w[i]=1ll*w[i] *sum%mod;
		invw[i]=inv(w[i]);
	}
}
int main() {
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
	init();
	work(); 
	int Q;scanf("%d",&Q); while(Q--) {
		int x,y; scanf("%d%d",&x,&y);
		printf("%d\n",ans[gett(x,y)]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

完