思路&做法

先將題目變換一下，對于每個卷軸 \((r_i, b_i) \leftarrow (n - r_i, m - b_i)\) ，要求從 \((0, 0)\) 走到 \((n, m)\) 的所有路徑的權值之和除以 \(\binom{n + m}{n}\) 。

設路徑 \(p\) 經過的卷軸依次為 \(q_1, q_2, \dots , q_t\)，上述文字轉化成式子即

分子中 \((2r_i + c_i - 2r_{i - 1} - c_{i - 1}) \times 2^{t - i + 1}\) 表示在從卷軸 \(q_{i - 1}\) 到卷軸 \(q_i\) 之間選擇的寶石會在第 \(q_i, q_{i + 1}, q_{i + 2}, \dots , q_{t}\) 個卷軸處進行 \(\times 2\) 的操作。

考慮簡化分子，分離 \(i - 1\) 和 \(i\) 可得

令 \(p_i\) 表示以 \((r_i, c_i)\) 為開頭，\((n, m)\) 為結尾的路徑，\(|p|\) 表示路徑 \(p_i\) 所經過的除 第\(i\) 個以外的卷軸數，上式變為

現在難在如何計算 \(\sum_{p_i} 2^{|p|}\) 。定義 \(f_i\) 為從卷軸 \(i\) 到 \((n, m)\) ，欽定經過若干卷軸的方案數，即

我們發現對于一條路徑 \(p_i\) ，它所經過的卷軸可以任意選擇 or 不選擇，即一條路徑在 \(f_i\) 中會被重復統計 \(2^{|p|}\) 次，所以 \(f_i = \sum_{p_i} 2^{|p|}\) ，所以

對于 \(f_i\) ，我們可以通過 \(O(N^2)\) 的預處理處理出來，轉移方程即 \(f_i = \sum_{r_j \geq r_i, c_j \geq c_i} f_j \times \binom{r_j + c_j - r_i - c_i}{ r_j - r_i}\) 。

最后發現在第 \(1\) 個卷軸前的寶石的路徑方案數未統計，所以還需 $\times \binom{r_i + c_i}{r_i} $ 。

最后答案為

solution

/*
address:https://codeforces.com/problemset/problem/2034/F2
AC 2025/8/18 17:29
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define mkp make_pair
const int N = 4e5 + 5, K = 5005;
const int mod = 998244353;
LL fac[N], inv[N];
inline void init() {s
    fac[0] = inv[0] = fac[1] = inv[1] = 1;
    for (int i = 2;i <= N - 5;++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    for (int i = 2;i <= N - 5;++i) inv[i] = inv[i - 1] * inv[i] % mod;
}
inline LL C(int n, int m) { return fac[n] * inv[m] % mod * inv[n - m] % mod; }
int n, m, k;
pii a[K];
LL f[K];
inline void trans(LL& x, LL y) { x = (x + y) % mod; }
int main() {
    init();
    int T;scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 1;i <= k;++i) scanf("%d%d", &a[i].first, &a[i].second), a[i] = mkp(n - a[i].first, m - a[i].second);
        a[++k] = mkp(0, 0);
        a[++k] = mkp(n, m);
        sort(a + 1, a + k + 1);
        f[k] = 1;
        for (int i = 1;i < k;++i) f[i] = 0;
        for (int i = k - 1;i >= 1;--i)
            for (int j = i + 1;j <= k;++j)
                if (a[j].second >= a[i].second)
                    trans(f[i], f[j] * C(a[j].first - a[i].first + a[j].second - a[i].second, a[j].first - a[i].first));
        LL ans = 0;
        for (int i = 1;i <= k;++i) trans(ans, C(a[i].first + a[i].second, a[i].first) * ((a[i].first << 1) + a[i].second) % mod * f[i] % mod);
        printf("%lld\n", ans * inv[n + m] % mod * fac[n] % mod * fac[m] % mod);
    }
    return 0;
}