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

Submission Time
Task F - Yes or No
User KoD
Language C++ (GCC 9.2.1)
Score 2000
Code Size 8460 Byte
Status AC
Exec Time 751 ms
Memory 32648 KiB

Judge Result

Set Name Sample Partial All
Score / Max Score 0 / 0 1500 / 1500 500 / 500
Status
AC × 5
AC × 28
AC × 75
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
Partial sample_01.txt, sample_02.txt, sample_04.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_2_01.txt, subtask_2_02.txt, subtask_2_03.txt, subtask_2_04.txt, subtask_2_05.txt, subtask_2_06.txt, subtask_2_07.txt, subtask_2_08.txt, subtask_2_09.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_28.txt, subtask_2_29.txt, subtask_2_30.txt, subtask_2_31.txt, subtask_2_32.txt, subtask_2_33.txt, subtask_2_34.txt, subtask_2_35.txt, subtask_2_36.txt, subtask_2_37.txt, subtask_2_38.txt, subtask_2_39.txt, subtask_2_40.txt
Case Name Status Exec Time Memory
sample_01.txt AC 10 ms 3576 KiB
sample_02.txt AC 3 ms 3652 KiB
sample_03.txt AC 3 ms 3600 KiB
sample_04.txt AC 4 ms 3588 KiB
sample_05.txt AC 4 ms 3512 KiB
subtask_1_01.txt AC 2 ms 3516 KiB
subtask_1_02.txt AC 2 ms 3604 KiB
subtask_1_03.txt AC 2 ms 3520 KiB
subtask_1_04.txt AC 2 ms 3580 KiB
subtask_1_05.txt AC 2 ms 3516 KiB
subtask_1_06.txt AC 2 ms 3520 KiB
subtask_1_07.txt AC 2 ms 3572 KiB
subtask_1_08.txt AC 2 ms 3520 KiB
subtask_1_09.txt AC 3 ms 3672 KiB
subtask_1_10.txt AC 2 ms 3612 KiB
subtask_1_11.txt AC 4 ms 3720 KiB
subtask_1_12.txt AC 8 ms 3704 KiB
subtask_1_13.txt AC 23 ms 4032 KiB
subtask_1_14.txt AC 42 ms 5048 KiB
subtask_1_15.txt AC 148 ms 8680 KiB
subtask_1_16.txt AC 147 ms 8804 KiB
subtask_1_17.txt AC 147 ms 8820 KiB
subtask_1_18.txt AC 148 ms 8804 KiB
subtask_1_19.txt AC 147 ms 8792 KiB
subtask_1_20.txt AC 147 ms 8800 KiB
subtask_1_21.txt AC 147 ms 8804 KiB
subtask_1_22.txt AC 146 ms 8820 KiB
subtask_1_23.txt AC 147 ms 8448 KiB
subtask_1_24.txt AC 144 ms 8072 KiB
subtask_1_25.txt AC 141 ms 8068 KiB
subtask_2_01.txt AC 3 ms 3512 KiB
subtask_2_02.txt AC 3 ms 3520 KiB
subtask_2_03.txt AC 3 ms 3516 KiB
subtask_2_04.txt AC 709 ms 30552 KiB
subtask_2_05.txt AC 700 ms 30568 KiB
subtask_2_06.txt AC 702 ms 30620 KiB
subtask_2_07.txt AC 701 ms 30496 KiB
subtask_2_08.txt AC 701 ms 30608 KiB
subtask_2_09.txt AC 704 ms 30688 KiB
subtask_2_10.txt AC 704 ms 30640 KiB
subtask_2_11.txt AC 705 ms 30620 KiB
subtask_2_12.txt AC 706 ms 30660 KiB
subtask_2_13.txt AC 701 ms 30692 KiB
subtask_2_14.txt AC 701 ms 30612 KiB
subtask_2_15.txt AC 704 ms 30552 KiB
subtask_2_16.txt AC 733 ms 32648 KiB
subtask_2_17.txt AC 751 ms 30356 KiB
subtask_2_18.txt AC 712 ms 27212 KiB
subtask_2_19.txt AC 672 ms 24068 KiB
subtask_2_20.txt AC 47 ms 16612 KiB
subtask_2_21.txt AC 48 ms 16860 KiB
subtask_2_22.txt AC 55 ms 16756 KiB
subtask_2_23.txt AC 62 ms 16816 KiB
subtask_2_24.txt AC 72 ms 18064 KiB
subtask_2_25.txt AC 71 ms 18924 KiB
subtask_2_26.txt AC 73 ms 18868 KiB
subtask_2_27.txt AC 74 ms 17912 KiB
subtask_2_28.txt AC 90 ms 18972 KiB
subtask_2_29.txt AC 101 ms 19120 KiB
subtask_2_30.txt AC 263 ms 22396 KiB
subtask_2_31.txt AC 428 ms 24236 KiB
subtask_2_32.txt AC 704 ms 30680 KiB
subtask_2_33.txt AC 728 ms 30684 KiB
subtask_2_34.txt AC 725 ms 30844 KiB
subtask_2_35.txt AC 740 ms 28560 KiB
subtask_2_36.txt AC 742 ms 28588 KiB
subtask_2_37.txt AC 313 ms 17656 KiB
subtask_2_38.txt AC 139 ms 15560 KiB
subtask_2_39.txt AC 722 ms 28260 KiB
subtask_2_40.txt AC 245 ms 22124 KiB