Submission #45210494

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

void solve(std::istream& is, std::ostream& os) {
    using Num = long long int;
    using ModInt = atcoder::modint998244353;
    Num n {0};
    Num a {0};
    Num b {0};
    Num p {0};
    Num q {0};
    is >> n >> a >> b >> p >> q;

    std::vector<ModInt> fst(n+1, 0);
    std::vector<ModInt> snd(n+1, 0);
    fst.at(a) = 1;
    snd.at(b) = 1;

    ModInt win {0};
    ModInt loss {0};
    for(Num turn{1}; turn<=n; ++turn) {
        ModInt f = 1;
        f -= loss;

        std::vector<ModInt> new_fst(n+1, 0);
        for(Num from{a}; from<n; ++from) {
            for(Num i{1}; i<=p; ++i) {
                Num d = std::min(n, from + i);
                auto r = fst.at(from);
                r /= p;
                new_fst.at(d) += r;
            }
        }

        if (f != 1) {
            win += new_fst.at(n) * f;
        } else {
            win += new_fst.at(n);
        }

        std::vector<ModInt> new_snd(n+1, 0);
        for(Num from{b}; from<n; ++from) {
            for(Num i{1}; i<=q; ++i) {
                Num d = std::min(n, from + i);
                auto r = snd.at(from);
                r /= q;
                new_snd.at(d) += r;
            }
        }
        loss += new_snd.at(n);

        if (loss == 1) {
            break;
        }

        std::swap(fst, new_fst);
        std::swap(snd, new_snd);
    }

    os << win.val() << "\n";
    return;
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result