最後の \(N\) 試合が行われる直前の最多勝利数を \(W\) とします。 優勝者の勝利数は \(W\) か \(W+1\) となることから、最後の \(N\) 試合が行われる直前の勝利数が \(W-2\) 以下の選手が優勝することはありません。 よって、これらの選手の勝利数を \(0\) にしても答えは変わりません。

この変更によって、最後の \(N\) 試合は以下のいずれかに分類されます。

• 勝利数が \(W\) の選手どうしが戦う
• 勝利数が \(W\) の選手と \(W-1\) の選手が戦う
• 勝利数が \(W\) の選手と \(0\) の選手が戦う
• 勝利数が \(W-1\) の選手どうしが戦う
• 勝利数が \(W-1\) の選手と \(0\) の選手が戦う
• 勝利数が \(0\) の選手どうしが戦う

それぞれの試合数を \(m _ 0,m _ 1,m _ 2,m _ 3,m _ 4,m _ 5\) とします。 それぞれの種類の試合を \(m _ 0\) の試合、\(m _ 1\) の試合などと呼ぶことにします。

すべての試合が終了した時点で勝利数が最多である選手を優勝候補者と呼ぶことにし、優勝候補者の人数と優勝候補者の勝利数の組ごとに確率を求め、最後に総和をとって答えを求めることを考えます。

優勝候補者の勝利数 \(W\) を固定したとき、試合は次のうちどちらかになることがわかります。

1. \(\dfrac12\) の確率で優勝候補者が \(1\) 人生じ、\(\dfrac12\) の確率で優勝候補者が \(0\) 人生じる
2. \(0\) 以上 \(1\) 以下の実数 \(p\) と正整数 \(k\) が存在し、\(p\) の確率で優勝候補者が \(k\) 人生じ、\(1-p\) の確率で矛盾する（固定した優勝候補者の勝利数より多い勝利数の選手が生じる）

これらをタイプ \(1\) の試合、タイプ \(2\) の試合と呼ぶことにします。

タイプ \(2\) の試合すべてにわたる \(p\) の総積を \(P\) 、\(k\) の総和を \(K\) とし、タイプ \(1\) の試合の個数を \(x\) とすると、優勝候補者の人数は \(K\) 人以上 \(K+x\) 人以下です。

タイプ \(1\) の試合に参加する勝利数が \(W\) になりうる選手をひとつとり、その選手を含めて優勝候補者が \(w\) 人 \((K+1\le w\le K+x)\) になる確率を考えます。 これは、その選手が参加する試合以外のタイプ \(1\) の試合の結果について考えることで \(P\times\dfrac{{} _ {x-1}\mathrm C_{w-K-1}}{2 ^ x}\) とわかります。

タイプ \(2\) の試合に参加する勝利数が \(W\) になりうる選手をひとつとり、その選手を含めて優勝候補者が \(w\) 人 \((K\le w\le K+x)\) になる確率を考えます。 矛盾しない条件のもとその選手の勝利数が \(W\) になる確率を \(q\) としたとき、同様にしてこれは \(qP\times\dfrac{{} _ {x}\mathrm C_{w-K}}{2 ^ x}\) とわかります。

1. 優勝者の勝利数が \(W+1\) の場合

このとき、\(m _ 1,m _ 2\) の試合はタイプ \(1\) の試合です。 それ以外の試合はタイプ \(2\) の試合で、\(m _ 0\) の試合は \(p=1,k=1\)、\(m _ 3,m _ 4,m _ 5\) の試合は \(p=1,k=0\) です。

よって、\(m _ 1,m _ 2\) の試合の勝利数が \(W\) の選手について、その選手を含めて優勝候補者が \(w\) 人 \((m _ 0+1\le w\le m _ 0+m _ 1+m _ 2)\) であるような確率は \(\dfrac{{} _ {m _ 1+m _ 2-1}\mathrm C _ {w - m _ 0-1}}{2 ^ {m _ 1+m _ 2}}\) となり、\(m _ 0\) の試合の選手についてその選手を含めて優勝候補者が \(w\) 人 \((m _ 0\le w\le m _ 0+m _ 1+m _ 2)\) であるような確率は \(\dfrac{{} _ {m _ 1+m _ 2}\mathrm C _ {w - m _ 0}}{2 ^ {m _ 1+m _ 2+1}}\) となります。

2. 優勝者の勝利数が \(W\) の場合

このとき、\(m _ 4\) の試合はタイプ \(1\) の試合です。 それ以外の試合はタイプ \(2\) の試合で、

• \(m _ 0\) の試合は \(p=0\)
• \(m _ 1\) の試合は \(p=\dfrac12,k=2\)
• \(m _ 2\) の試合は \(p=\dfrac12,k=1\)
• \(m _ 3\) の試合は \(p=1,k=1\)
• \(m _ 5\) の試合は \(p=1,k=0\)

です。

これをもとに、同様に計算を行うことで確率を求めることができます。

---

事前に階乗の前計算などをしておくことで、ある程度の範囲の二項係数を定数時間で計算できるようにします。 勝利数が \(W\) の場合と \(W+1\) の場合それぞれにおける \(\dfrac P{2 ^ x}\) の値も計算しておくことで、上述の確率を定数時間で得ることができます。 階乗の前計算を行っているので、優勝候補者の人数の逆数も定数時間で得ることができます。

これらを合計することで、この問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <numeric>
#include <ranges>
#include <array>
#include <atcoder/modint>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    unsigned N;
    cin >> N;

    // 階乗前計算
    vector<modint> fact(2 * N + 1), ifact(2 * N + 1);
    iota(begin(fact), end(fact), modint{});
    fact.front() = 1;
    inclusive_scan(begin(fact), end(fact), begin(fact), multiplies{});
    iota(begin(ifact), end(ifact), modint{1});
    ifact.back() = 1 / fact.back();
    inclusive_scan(rbegin(ifact), rend(ifact), rbegin(ifact), multiplies{});
    const auto binom{[&fact, &ifact](const unsigned n, const unsigned r) {
        return fact[n] * ifact[r] * ifact[n - r];
    }};
    const auto inv{[&fact, &ifact](const unsigned n) {
        return ifact[n] * fact[n - 1];
    }};

    vector<pair<unsigned, unsigned>> match(N);
    unsigned max_win{};
    for (auto&& [L, R] : match) {
        cin >> L >> R;
        max_win = max({max_win, L, R});
    }

    // 試合を分類する
    const auto match_type{[max_win](unsigned L, unsigned R){
        if (L > R)
            swap(L, R);
        if (R == max_win) {
            if (L == max_win) return 0;
            if (L + 1 == max_win) return 1;
            return 2;
        }
        if (R + 1 == max_win) {
            if (L + 1 == max_win) return 3;
            return 4;
        }
        return 5;
    }};

    // それぞれの種類の試合がいくつあるか数える
    array<unsigned, 6> match_count{};
    for (const auto& [L, R] : match)
        ++match_count[match_type(L, R)];

    // それぞれの種類の (勝ち数が少なくないほう, 勝ち数が多くないほう) が優勝する確率を求める
    array<pair<modint, modint>, 6> prob{};

    // 優勝候補者が勝った回数が max_win + 1 回の場合
    {
        const auto winner_min{match_count[0]}, winner_max{match_count[0] + match_count[1] + match_count[2]};
        const auto coef{modint::raw(2).pow(match_count[1] + match_count[2]).inv()};
        if (winner_min) {
            for (const auto w : views::iota(winner_min, winner_max + 1)) {
                const auto p{binom(winner_max - winner_min, w - winner_min) * coef * inv(w)};
                prob[0].first += p * ((998244353 + 1) / 2);
                prob[0].second += p * ((998244353 + 1) / 2);
            }
        }
        for (const auto w : views::iota(winner_min + 1, winner_max + 1)) {
            const auto p{binom(winner_max - winner_min - 1, w - winner_min - 1) * coef * inv(w)};
            prob[1].first += p;
            prob[2].first += p;
        }
    }

    // 優勝候補者が勝った回数が max_win 回の場合
    if (match_count[0] == 0) {
        const auto winner_min{2 * match_count[1] + match_count[2] + match_count[3]}, winner_max{2 * match_count[1] + match_count[2] + match_count[3] + match_count[4]};
        const auto coef{modint::raw(2).pow(match_count[1] + match_count[2] + match_count[4]).inv()};
        if (winner_min) {
            for (const auto w : views::iota(winner_min, winner_max + 1)) {
                const auto p{binom(winner_max - winner_min, w - winner_min) * coef * inv(w)};
                prob[1].first += p;
                prob[1].second += p;
                prob[2].first += p;
                prob[3].first += p * ((998244353 + 1) / 2);
                prob[3].second += p * ((998244353 + 1) / 2);
            }
        }
        for (const auto w : views::iota(winner_min + 1, winner_max + 1)) {
            const auto p{binom(winner_max - winner_min - 1, w - winner_min - 1) * coef * inv(w)};
            prob[4].first += p;
        }
    }

    for (const auto& [L, R] : match) {
        const auto& [a_large, a_small]{prob[match_type(L, R)]};
        if (L < R)
            cout << a_small.val() << " " << a_large.val() << " ";
        else
            cout << a_large.val() << " " << a_small.val() << " ";
    }
    cout << endl;
    return 0;
}