代码

#include <cstdio>
#include <algorithm>
#define M_MAX 1000
#define L_MAX 2048
#define R_MAX 12
#define lld "%llu"
typedef unsigned long long lnt;
typedef unsigned unt;
typedef void vnt;
const unt P = 998244353, G = 3;
inline lnt moc(lnt a) { return a < P ? a : a - P; }
inline lnt mod(lnt a) { return a < P ? a : a % P; }
inline lnt qow(lnt a, unt k)
{
    static lnt w;
    for (w = 1; k; a = mod(a * a), k >>= 1)
        if (k & 1) w = mod(w * a);
    return w;
}
inline lnt inv(lnt a)
{
    lnt v = 1;
    while (a > 1) v = mod(v * (P - P / a)), a = P % a;
    return v;
}
int l, r, rev[L_MAX + 1];
lnt w[R_MAX];
inline vnt cpy(int n, lnt a[], lnt b[])
{
    for (int i = 0; i < n; ++i)
        b[i] = a[i];
}
inline vnt rvs(int n, lnt a[], lnt b[])
{
    for (int i = 0; i < n; ++i)
        b[i] = a[n - i - 1];
}
inline vnt fft(lnt a[])
{
    int i, j, k, r = ::r; lnt x, u, v;
    for (i = 1; i < l; ++i)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);
    for (k = 1, --r; k < l; k <<= 1, --r)
        for (i = 0; i < l; i += k << 1)
            for (j = 0, x = 1; j < k; ++j, x = mod(x * w[r]))
                u = a[i + j], v = mod(x * a[i + j + k]), a[i + j] = moc(u + v), a[i + j + k] = moc(u - v + P);
}
inline vnt mul(int m, lnt a[], int n, lnt b[], lnt c[])
{
    static lnt x[L_MAX + 1], y[L_MAX + 1];
    for (l = 1, r = 0; l < m + n - 1; l <<= 1, ++r);
    for (int i = 1; i < l; ++i)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (r - 1));
    w[0] = qow(G, (P - 1) >> r);
    for (int i = 0; i < r - 1; ++i)
        w[i + 1] = mod(w[i] * w[i]);
    if (a == b)
    {
        cpy(m, a, x), fft(x);
        for (int i = 0; i < l; ++i)
            x[i] = mod(x[i] * x[i]);
    }
    else
    {
        cpy(m, a, x), fft(x), cpy(n, b, y), fft(y);
        for (int i = 0; i < l; ++i)
            x[i] = mod(x[i] * y[i]), y[i] = 0;
    }
    w[0] = inv(w[0]);
    for (int i = 0; i < r - 1; ++i)
        w[i + 1] = mod(w[i] * w[i]);
    fft(x);
    lnt v = inv(l);
    for (int i = 0; i < m + n - 1; ++i)
        c[i] = mod(x[i] * v);
    for (int i = 0; i < l; ++i)
        x[i] = 0;
}
inline vnt inv(int n, lnt a[], lnt b[])
{
    static lnt x[L_MAX + 1], y[L_MAX + 1];
    if (n == 1)
        b[0] = inv(a[0]);
    else
    {
        inv((n + 1) >> 1, a, b);
        cpy(n, a, x), cpy((n + 1) >> 1, b, y);
        for (l = 1, r = 0; l < (n << 1) - 1; l <<= 1, ++r);
        for (int i = 1; i < l; ++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (r - 1));
        w[0] = qow(G, (P - 1) >> r);
        for (int i = 0; i < r - 1; ++i)
            w[i + 1] = mod(w[i] * w[i]);
        fft(x), fft(y);
        for (int i = 0; i < l; ++i)
            x[i] = mod(moc(2 - mod(x[i] * y[i]) + P) * y[i]);
        w[0] = inv(w[0]);
        for (int i = 0; i < r - 1; ++i)
            w[i + 1] = mod(w[i] * w[i]);
        fft(x);
        lnt v = inv(l);
        for (int i = 0; i < n; ++i)
            b[i] = mod(x[i] * v);
        for (int i = 0; i < l; ++i)
            x[i] = 0, y[i] = 0;
    }
}
int n, m;
lnt p, q, e[M_MAX + 1], f[2][M_MAX * 2 + 1], g[M_MAX + 1], a[M_MAX + 1], b[M_MAX * 2 + 1], c[M_MAX * 2 + 1];
inline vnt div(int m, lnt a[], int n, lnt b[])
{
    static lnt d[M_MAX * 2 + 1], e[M_MAX * 2 + 1];
    rvs(m, a, d);
    mul(m - n + 1, c, m - n + 1, d, e);
    rvs(m - n + 1, e, b);
}
inline vnt sol(int n, int m)
{
    static lnt d[M_MAX * 2 + 1];
    if (n == 1)
    {
        rvs(m, a, d), inv(m, d, c);
        for (int i = 0; i < m; ++i)
            b[i] = a[i];
    }
    else if (n & 1)
    {
        sol(n ^ 1, m);
        lnt b0 = b[0];
        for (int i = 0; i < m - 1; ++i)
            b[i] = mod(a[i] * b0 + b[i + 1]);
        b[m - 1] = mod(a[m - 1] * b0);
    }
    else
    {
        sol(n >> 1, m);
        mul(m, b, m, b, b);
        div((m << 1) - 1, b, m, d);
        d[0] = 0;
        for (int i = 0; i < m - 1; ++i)
            b[i] = moc(b[i] + d[i + 1]);
        mul(m, a, m, d, d);
        for (int i = 0; i < (m << 1) - 1; ++i)
            b[i] = moc(b[i] - d[i] + P);
    }
}
inline lnt cal(int m)
{
    static int o, k, l, i, j;
    f[o][0] = 1, f[o][k = 1] = e[m];
    for (j = 2; j <= m; ++j)
        f[0][j] = 0, f[1][j] = 0, g[j] = 0;
    for (i = m - 1; i >= 0; --i)
    {
        o ^= 1;
        l = k, k = std::min(n, m / std::max(1, i));
        g[0] = 1;
        for (j = 0; j <= std::min(l, k - 1); ++j)
            g[j + 1] = mod(moc(P - e[i]) * f[o ^ 1][j]);
        inv(k + 1, g, f[o]);
        mul(k + 1, f[o], l + 1, f[o ^ 1], f[o]);
    }
    if (n <= m)
        return f[o][n];
    for (j = 0; j <= m; ++j)
        a[j] = mod(e[0] * f[o ^ 1][j]);
    sol(n - m, m + 1);
    lnt s = 0;
    for (j = 0; j <= m; ++j)
        s = mod(s + b[j] * f[o][m - j]);
    return s;
}
int main()
{
    scanf("%d %d" lld lld, &n, &m, &p, &q);
    p = mod(p * inv(q));
    e[0] = moc(1 - p + P);
    for (int i = 1; i <= m; ++i)
        e[i] = mod(e[i - 1] * p);
    printf(lld "\n", moc(cal(m) - cal(m - 1) + P));
    return 0;
}

评测结果