Submission #31453926

---

Source Code Expand

// #define NDEBUG
#include <bits/stdc++.h>

namespace kod {

using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;

using f64 = double;
using f80 = long double;

}  // namespace kod

/**
 * @brief 数値型のエイリアス
 */

namespace kod {
namespace util {

template <class F>
struct FixedPoint : private F {
    explicit constexpr FixedPoint(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args>
    constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class F>
constexpr FixedPoint<F> fixed(F&& f) {
    return FixedPoint<F>(std::forward<F>(f));
}

}  // namespace util
}  // namespace kod

/**
 * @brief 不動点コンビネータ
 */

namespace kod {
namespace util {

class ForwardRange {
    int src, dst;

  public:
    explicit constexpr ForwardRange(const int l, const int r) : src(l), dst(r) {}
    explicit constexpr ForwardRange(const int n) : src(0), dst(n) {}
    constexpr ForwardRange begin() const { return *this; }
    constexpr std::monostate end() const { return {}; }
    constexpr bool operator!=(std::monostate) const { return src < dst; }
    constexpr void operator++() const {}
    constexpr int operator*() { return src++; }
};

class BackwardRange {
    int src, dst;

  public:
    explicit constexpr BackwardRange(const int l, const int r) : src(r), dst(l) {}
    explicit constexpr BackwardRange(const int n) : src(n), dst(0) {}
    constexpr BackwardRange begin() const { return *this; }
    constexpr std::monostate end() const { return {}; }
    constexpr bool operator!=(std::monostate) const { return src > dst; }
    constexpr void operator++() const {}
    constexpr int operator*() { return --src; }
};

using rep = ForwardRange;
using revrep = BackwardRange;

}  // namespace util
}  // namespace kod

/**
 * @brief 昇順・降順走査
 */

namespace kod {
namespace util {

template <class T>
constexpr bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
constexpr bool setmax(T& x, const T& y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

}  // namespace util
}  // namespace kod

/**
 * @brief 比較代入
 */

namespace kod {
namespace util {

template <class T>
void print(T&& x) {
    std::cout << x;
}

template <class T, class... Args>
void print(T&& x, Args&&... args) {
    std::cout << x << ' ';
    print(std::forward<Args>(args)...);
}

void println() {
    std::cout << '\n';
}

template <class... Args>
void println(Args&&... args) {
    print(std::forward<Args>(args)...);
    std::cout << '\n';
}

template <class C>
void print_seq(C&& c, const char* sep = " ", const char* end = "\n") {
    bool f = false;
    for (auto&& x : std::forward<C>(c)) {
        if (f) {
            std::cout << sep;
        } else {
            f = true;
        }
        std::cout << x;
    }
    std::cout << end;
}

}  // namespace util
}  // namespace kod

/**
 * @brief 標準出力ユーティリティ
 */

namespace kod {
namespace util {

template <class T>
T scan() {
    T x;
    std::cin >> x;
    return x;
}

template <class T>
std::vector<T> scan_vec(int n = -1) {
    if (n == -1)
        std::cin >> n;
    assert(n >= 0);
    std::vector<T> v(n);
    for (auto& x : v)
        std::cin >> x;
    return v;
}

template <class T, int N>
std::array<T, N> scan_array() {
    std::array<T, N> a;
    for (auto& x : a)
        std::cin >> x;
    return a;
}

std::vector<char> scan_chars() {
    std::string s;
    std::cin >> s;
    return std::vector<char>(std::cbegin(s), std::cend(s));
}

}  // namespace util
}  // namespace kod

/**
 * @brief 標準入力ユーティリティ
 */

#include <atcoder/convolution>
#include <atcoder/modint>

namespace ext {

template <class M>
struct FpUtil {
    static M fact(const int n) {
        static std::vector<M> vec;
        assert(n >= 0);
        if (vec.empty())
            vec = {M(1)};
        for (int i = vec.size(); i <= n; ++i)
            vec.push_back(vec.back() * M(i));
        return vec[n];
    }
    static M inv(const int n) {
        static std::vector<M> vec;
        assert(n > 0);
        if (vec.empty())
            vec = {M(0), M(1)};
        for (int i = vec.size(); i <= n; ++i)
            vec.push_back(-M(M::mod() / i) * vec[M::mod() % i]);
        return vec[n];
    }
    static M inv_fact(const int n) {
        static std::vector<M> vec;
        assert(n >= 0);
        if (vec.empty())
            vec = {M(1)};
        for (int i = vec.size(); i <= n; ++i)
            vec.push_back(vec.back() * inv(i));
        return vec[n];
    }
    static M binom(const int n, const int k) {
        assert(0 <= k and k <= n);
        return fact(n) * inv_fact(n - k) * inv_fact(k);
    }
    static M factpow(const int n, const int k) {
        assert(0 <= k and k <= n);
        return fact(n) * inv_fact(n - k);
    }
    static M homo(const int n, const int k) {
        assert((n == 0 and k == 0) or (n > 0 and k >= 0));
        if (n == 0 and k == 0)
            return M(1);
        return binom(n + k - 1, k);
    }
};

}  // namespace ext

namespace solution {

using namespace kod;
using namespace util;

using std::array;
using std::pair;
using std::tuple;
using std::vector;

constexpr i32 inf32 = std::numeric_limits<i32>::max() / 2;
constexpr i64 inf64 = std::numeric_limits<i64>::max() / 2;

using Fp = atcoder::modint998244353;
using Util = ext::FpUtil<Fp>;

Fp inv_binom(const int n, const int k) {
    return Util::inv_fact(n) * Util::fact(n - k) * Util::fact(k);
}

void main() {
    const int n = scan<int>();
    const int m = scan<int>();
    // Fp ans = 0;
    // for (const int i : rep(n + 1)) {
    //     for (const int j : rep(m + 1)) {
    //         ans += Fp(std::max(i, j)) * Util::binom(n, i) * Util::binom(m, j) / Util::binom(n
    //         + m, i + j) / (i + j);
    //     }
    // }
    vector<Fp> f1(n + 1), f2(n + 1), g1(m + 1), g2(m + 1);
    for (const int i : rep(n + 1)) {
        f1[i] = Util::binom(n, i);
        f2[i] = f1[i] * i;
    }
    for (const int j : rep(m + 1)) {
        g1[j] = Util::binom(m, j);
        g2[j] = g1[j] * j;
    }
    vector<Fp> h(n + m + 1);
    fixed([&](auto&& dfs, const int l, const int r) -> void {
        if (l > n or l > m) {
            return;
        }
        if (r - l <= 60) {
            for (const int i : rep(l, std::min(n + 1, r))) {
                for (const int j : rep(l, std::min(m + 1, r))) {
                    if (i < j) {
                        h[i + j] += f1[i] * g2[j];
                    }
                    if (j < i) {
                        h[i + j] += f2[i] * g1[j];
                    }
                }
            }
            return;
        }
        const int mid = (l + r) / 2;
        dfs(l, mid);
        dfs(mid, r);
        if (mid <= m) {
            vector<Fp> f(f1.begin() + l, f1.begin() + std::min(n + 1, mid));
            vector<Fp> g(g2.begin() + mid, g2.begin() + std::min(m + 1, r));
            auto tmp = atcoder::convolution(std::move(f), std::move(g));
            for (const int k : rep(tmp.size())) {
                h[k + l + mid] += tmp[k];
            }
        }
        if (mid <= n) {
            vector<Fp> f(f2.begin() + mid, f2.begin() + std::min(n + 1, r));
            vector<Fp> g(g1.begin() + l, g1.begin() + std::min(m + 1, mid));
            auto tmp = atcoder::convolution(std::move(f), std::move(g));
            for (const int k : rep(tmp.size())) {
                h[k + l + mid] += tmp[k];
            }
        }
    })(0, n + m + 1);
    Fp ans = 0;
    for (const int k : rep(1, std::min(n, m) + 1)) {
        ans += Util::binom(n, k) * Util::binom(m, k) * inv_binom(n + m, k + k) *
               Util::inv(k + k) * k;
    }
    for (const int k : rep(1, n + m + 1)) {
        ans += h[k] * inv_binom(n + m, k) * Util::inv(k);
    }
    println(ans.val());
}

}  // namespace solution

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(20);
    int cases = 1;
    // std::cin >> cases;
    while (cases--)
        solution::main();
    return 0;
}

Submission Info

Judge Result