LOJ

分析

不难想到一个 $\mathcal{O}(n^3m^3)$ 的高斯消元做法，即将每个位置出发的期望步数作为变量，然后暴力高斯消元。

考虑将第一行、第二行、第一列的位置作为主元，并将其它元用主元线性表示。可以发现只有 $(x+2,y+1)$ 无法直接求出它的线性表示，但因为向八个方向走的概率之和为 $1$，所以可以用其它七个方向来求 $(x+2,y+1)$ 的线性表示。

当 $(x+2,y+1)$ 在棋盘外时，此时期望步数为 $0$，因此可以列出关于主元的方程。

这样子就产生了只有 $\mathcal{O}(n)$ 个元的方程组，直接高斯消元即可。询问时利用线性表示计算出值。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200+10;
const int dx[8]={-2,-1,1,2,2,1,-1,-2};
const int dy[8]={-1,-2,-2,-1,1,2,2,1};
const int mod=998244353;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}
void add(int& x,int y) { x=(x+y)%mod; }
void sub(int& x,int y) { x=(x-y+mod)%mod; }
void mul(int& x,int y) { x=1ll*x*y%mod; }

int n,m,p[10],coe[N][N][N*5],cnt,A[N*5][N*5],P[N*5],tot;

void Gauss(int n) {
    for (int i=1;i<=n;++i) {
        int p=i;
        for (int j=i;j<=n;++j) if (A[j][i]) { p=j; break; }
        if (p!=i) swap(A[i],A[p]);
        for (int j=1;j<=n;++j) {
            if (i==j) continue;
            int r=1ll*A[j][i]*qpow(A[i][i],mod-2)%mod;
            for (int k=1;k<=n+1;++k) sub(A[j][k],1ll*r*A[i][k]%mod);
        }
    }
    for (int i=1;i<=n;++i) P[i]=1ll*A[i][n+1]*qpow(A[i][i],mod-2)%mod;
}

int main() {
    n=read(),m=read(); int isp=0;
    for (int i=0;i<8;++i) p[i]=read(),isp=(isp+p[i])%mod;
    isp=qpow(isp,mod-2);
    for (int i=0;i<8;++i) p[i]=1ll*p[i]*isp%mod;
    for (int i=1;i<=2;++i)
        for (int j=1;j<=m;++j) coe[i][j][++cnt]=1;
    for (int i=3;i<=n;++i) coe[i][1][++cnt]=1;
    int invp4=qpow(p[4],mod-2);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            if (i+2<=n&&j+1<=m) {
                for (int k=1;k<=cnt+1;++k) coe[i+2][j+1][k]=coe[i][j][k];
                sub(coe[i+2][j+1][cnt+1],1);
                for (int d=0;d<8;++d) {
                    if (d==4) continue;
                    int x=i+dx[d],y=j+dy[d];
                    if (x<1||x>n|y<1||y>m) continue;
                    for (int k=1;k<=cnt+1;++k)
                        sub(coe[i+2][j+1][k],1ll*p[d]*coe[x][y][k]%mod);
                }
                for (int k=1;k<=cnt+1;++k) mul(coe[i+2][j+1][k],invp4);
            } else {
                ++tot;
                for (int k=1;k<=cnt+1;++k) A[tot][k]=coe[i][j][k];
                sub(A[tot][cnt+1],1);
                for (int d=0;d<8;++d) {
                    if (d==4) continue;
                    int x=i+dx[d],y=j+dy[d];
                    if (x<1||x>n||y<1||y>m) continue;
                    for (int k=1;k<=cnt+1;++k)
                        sub(A[tot][k],1ll*p[d]*coe[x][y][k]%mod);
                }
                for (int k=1;k<=cnt+1;++k) mul(A[tot][k],invp4);
                A[tot][cnt+1]=mod-A[tot][cnt+1];
            }
        }
    Gauss(cnt);
    int Q=read();
    while (Q--) {
        int x=read(),y=read(),ans=coe[x][y][cnt+1];
        for (int i=1;i<=cnt;++i) add(ans,1ll*coe[x][y][i]*P[i]%mod);
        printf("%d\n",ans);
    }
    return 0;
}