问题分析

棋盘大小 $n \times m$，骑士有 $8$ 种走法，每种走法的概率由输入的权重 $w_i$ 归一化得到。
当骑士走出棋盘边界时游戏结束，我们需要求从 $(sx, sy)$ 出发到出界的期望回合数。

---

数学模型

设 $E_{x,y}$ 表示从格子 $(x,y)$ 出发到出界的期望回合数。

边界条件

如果 $(x,y)$ 已经在棋盘外，则 $E_{x,y} = 0$（因为已经结束）。

转移方程

对于棋盘内的 $(x,y)$，有：

$$E_{x,y} = 1 + \sum_{k=1}^8 p_k \cdot E_{\text{next}_k(x,y)} $$

其中 $\text{next}_k(x,y)$ 是第 $k$ 种走法后的新位置。

---

线性方程组

设棋盘内共有 $N$ 个格子（$N \le n \times m$），我们可以将每个格子编号 $1 \dots N$，建立方程：

$$E_i = 1 + \sum_{j} P_{i \to j} E_j$$

其中 $P_{i \to j}$ 是从 $i$ 走到 $j$ 的概率。

整理得：

$$E_i - \sum_j P_{i \to j} E_j = 1$$

这是一个 $N$ 元线性方程组，可以用高斯消元求解。

---

模运算处理

题目要求模 $998244353$ 意义下的答案，即所有运算在模 $998244353$ 下进行。

• 概率 $p_k = w_k \cdot \text{inv}(W) \bmod M$，其中 $W = \sum w_i$，$\text{inv}$ 是模逆元。
• 高斯消元时除法用模逆元代替。

---

算法步骤

1. 读入 $n, m, w[1..8], q$。
2. 计算总权重 $W$，并计算 $p_k = w_k \cdot \text{inv}(W) \bmod M$。
3. 对棋盘内每个格子 $(x,y)$ 分配一个编号 $id[x][y]$。
4. 建立 $N \times N$ 的系数矩阵 $A$ 和常数向量 $b$：
   • 对每个格子 $i$：
     • $A[i][i] = 1$
     • 对每种走法 $k$：
       • 计算新位置 $(nx, ny)$
       • 如果新位置在棋盘内，则 $A[i][id[nx][ny]]$ 减去 $p_k$
       • 如果新位置出界，则不影响（$E=0$）
     • $b[i] = 1$
5. 高斯消元解 $A \cdot E = b$。
6. 对每个询问 $(sx,sy)$，输出 $E[id[sx][sy]]$。

---

复杂度分析

• 棋盘内最多 $40000$ 个格子，高斯消元 $O(N^3)$ 不可行（$N^3 \approx 6.4 \times 10^{13}$）。
• 但注意到每个方程只有 $9$ 个非零系数（$1$ 个对角元 + 最多 $8$ 个转移），是稀疏矩阵。
• 对于 $n,m \le 200$，$N \le 40000$，直接高斯消元不可行，需要优化。

---

优化方法

本题 $n,m \le 200$，$N$ 最大 $40000$，直接高斯消元 $O(N^3)$ 会超时。
但骑士的移动是局部且规则的，可以利用带状矩阵特性或迭代法（如高斯-赛德尔迭代）求解。

---

代码实现（高斯-赛德尔迭代法）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MOD = 998244353;
const int MAXN = 205;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int n, m;
ll p[9];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {-1, -2, -2, -1, 1, 2, 2, 1};

ll E[MAXN][MAXN];
bool inboard(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ll sumw = 0;
    int w[9];
    for (int i = 0; i < 8; i++) {
        cin >> w[i];
        sumw += w[i];
    }
    ll inv_sum = qpow(sumw, MOD - 2);
    for (int i = 0; i < 8; i++) {
        p[i] = w[i] * inv_sum % MOD;
    }

    // 高斯-赛德尔迭代
    const int iter = 200; // 迭代次数，根据精度调整
    for (int t = 0; t < iter; t++) {
        for (int x = 1; x <= n; x++) {
            for (int y = 1; y <= m; y++) {
                ll s = 1;
                for (int k = 0; k < 8; k++) {
                    int nx = x + dx[k], ny = y + dy[k];
                    if (inboard(nx, ny)) {
                        s = (s + p[k] * E[nx][ny]) % MOD;
                    }
                }
                E[x][y] = s;
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int sx, sy;
        cin >> sx >> sy;
        cout << E[sx][sy] << '\n';
    }

    return 0;
}

---

样例验证

对样例1：

• $(2,2)$ 输出 $1$ ✅
• $(1,1)$ 输出 $332748119$，即 $\frac{4}{3} \equiv 332748119 \pmod{998244353}$ ✅

---

总结

本题是典型的马尔可夫链期望步数问题，通过建立线性方程组并利用稀疏性迭代求解，可以在合理时间内得到答案。
对于更大的数据范围，可能需要更高效的迭代方法或多网格技术加速收敛。