HDU

分析

将问题看做平面上的游走，每步有 $a = \frac{pq}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n - 1, m - 1)$、$b = \frac{p(1 - q)}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n, m - 1)$、$c = \frac{(1 - p)q}{1 - (1 - p)(1 - q)}$ 的概率移动到 $(n - 1, m)$。

假设最后 Alice 剩余血量为 $x$，那么会先游走到 $(x, 1)$，然后往下走，这一步的概率为 $d = \frac{p}{1 - (1 - p)(1 - q)}$。

枚举 $a$ 的次数，可以得到答案为
$$
d \sum_{x = 1}^n \sum_{i = 0}^{\min\{n - x, m - 1\}} {m - 1 + n - x - i \choose i, m - 1 - i, n - x - i} a^i b^{m - 1 - i} c^{n - x - i}
$$
交换求和号
$$
d \sum_{i = 0}^{\min\{n - 1, m - 1\}} \frac{1}{i! (m - 1 - i)!} a^i b^{m - 1 - i} \sum_{x = 1}^n \frac{(m - 1 + n - x - i)!}{(n - x - i)!} c^{n - x - i}
$$
改为枚举 $n - x - i$
$$
d \sum_{i = 0}^{\min\{n - 1, m - 1\}} \frac{1}{i! (m - 1 - i)!} a^i b^{m - 1 - i} \sum_{x = 1}^n \frac{(m - 1 + i)!}{i!} c^{i}
$$
后面的东西可以 $\mathcal{O}(n)$ 预处理，整个式子可以 $\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)
#define debug(...) fprintf(stderr, __VA_ARGS__)
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 = 10000000 + 10;
const int mod = 998244353, inv100 = 828542813;
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;
}

int n, m, p, q;
int fac[N], ifac[N], s[N];
int pwa[N], pwb[N], pwc[N];

void InitFac(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for (int i = n; i; --i) ifac[i - 1] = 1ll * ifac[i] * i % mod;
}

int main() {
    int T = read();
    while (T--) {
        n = read(), m = read(), p = 1ll * read() * inv100 % mod, q = 1ll * read() * inv100 % mod;
        InitFac(n + m);
        int _ = (1 - 1ll * (1 - p + mod) * (1 - q + mod) % mod + mod) % mod;
        int a = 1ll * p * q % mod * qpow(_, mod - 2) % mod;
        int b = 1ll * p * (1 - q + mod) % mod * qpow(_, mod - 2) % mod;
        int c = 1ll * (1 - p + mod) * q % mod * qpow(_, mod - 2) % mod;
        int d = 1ll * p * qpow(_, mod - 2) % mod;
        pwa[0] = pwb[0] = pwc[0] = 1;
        for (int i = 1; i <= min(n - 1, m - 1); ++i) pwa[i] = 1ll * pwa[i - 1] * a % mod;
        for (int i = 1; i <= m - 1; ++i) pwb[i] = 1ll * pwb[i - 1] * b % mod;
        for (int i = 1; i <= n - 1; ++i) pwc[i] = 1ll * pwc[i - 1] * c % mod;
        s[0] = fac[m - 1];
        for (int i = 1; i <= n - 1; ++i)
            s[i] = (s[i - 1] + 1ll * fac[m - 1 + i] * ifac[i] % mod * pwc[i]) % mod;
        int ans = 0;
        for (int i = 0; i <= min(n - 1, m - 1); ++i)
            ans = (ans + 1ll * ifac[i] * ifac[m - 1 - i] % mod * pwa[i] % mod * pwb[m - 1 - i] % mod * s[n - 1 - i]) % mod;
        ans = 1ll * ans * d % mod;
        printf("%d\n", ans);
    }
    return 0;
}