Submission #1544804

---

Source Code Expand

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;

const int MAXN = 1000001;

const int MOD = 998244353;

class Num {
    ll value;

    static Num& convert(ll& v) {
        return reinterpret_cast<Num&>(v).mod();
    }

    static Num convert(ll&& v) {
        return v;
    }

public:

    Num(ll v = 0)
        : value(v) {
        mod();
    }

    Num& mod() {
        value %= MOD;
        return *this;
    }

#define Op(op) decltype(auto) operator op(const Num& other) {return convert(value op other.value);}

    explicit operator ll() {
        return value;
    }

    Op(+) Op(*) Op(-) Op(+=) Op(*=)
};

ll pw(ll a, int b = MOD - 2) {
    if (b == 0) return 1;
    ll v = pw(a, b / 2);
    v = (v * v) % MOD;
    if (b & 1) v = (v * a) % MOD;
    return v;
}

Num rever(Num other) {
    return pw(ll(other));
} 

Num fact[MAXN];
Num rev[MAXN];
const Num rev2 = (MOD + 1) / 2;

Num cnk(ll n, ll m) {
    return fact[n + m] * rev[m] * rev[n];
}

    
int main() {
#ifdef PAUNSVOKNO
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20);
    int n, m;
    cin >> n >> m;
    int s = n + m;
    fact[0] = 1;
    for (int i = 1; i <= s; i++) {
        fact[i] = fact[i - 1] * i;
    }

    rev[s] = rever(fact[s]);

    for (int i = s - 1; i >= 0; i--)
        rev[i] = rev[i + 1] * (i + 1);

    Num ans = cnk(n, m) * (2ll * max(n, m) - 1);

    for (int i = 0; i <= min(n, m); i++) {
        ans += cnk(i, i) * cnk(n - i, m - i);
    }

    ans *= rever(cnk(n, m));
    ans *= rever(2);

    cout << ll(ans) << "\n";
}

Submission Info

Judge Result