Submission #1551070

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

const int L = 1E6 + 10;

ll F[L], I[L];

ll MOD = 998244353;

ll power(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b % 2) res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

void init() {
	F[0] = 1;
	for (int i = 1;i <= 1000000;i++) F[i] = (F[i - 1] * i) % MOD;
	I[1000000] = power(F[1000000], MOD - 2);
    for (int i = 1000000;i >= 1;i--) I[i - 1] = (I[i] * i) % MOD;
    return;
}

ll inv(ll x) {
	return (I[x] * F[x - 1]) % MOD;
}

ll nchoosek(ll x, ll y) {
	return (F[x] * ((I[y] * I[x - y]) % MOD)) % MOD;
}

ll cal(int a, int b, int A, int B) {
	if (a > A || b > B) return 0;
	ll sol = nchoosek(a + b, a) * nchoosek(A + B - a - b, A - a);
	sol %= MOD;
	sol *= power(nchoosek(A + B, A), MOD - 2);
	sol %= MOD;
	return sol;
}

ll solve(int N, int M) {
	// Type A: N, Type B: M.
	ll p = (N * inv(N + M)) % MOD; // specific position is A.
	ll res = 1; // Last element is A.
	ll crt = 1; // Num of A is strictly bigger than B
	ll eq = 0;
	for (int i = 1;i < N + M;i++) {
		// Update probability.
		int j = i - 1;
		if (j % 2 == 0) {
			ll now = crt;
			eq = cal(j / 2, j / 2 + 1, N - 1, M);
			now += MOD - (((eq * (j / 2 + 1)) % MOD) * inv(j + 1)) % MOD;
			now %= MOD;
			res += (eq * inv(2)) % MOD;
			res %= MOD;
			crt = now;
		}
		else {
			ll now = crt;
			if (eq > 0) {
				int a = j / 2;
				int b = j / 2 + 1;
				if (N - 1 > a) {
					eq *= (N - 1 - a);
					eq %= MOD;
					eq *= inv(N + M - 1 - a - b);
					eq %= MOD;
					now += eq;
					now %= MOD;
				}
			}
			crt = now;
		}
		res += crt;
		res %= MOD;
	}
	return (res * p) % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    init();
    ll sol = solve(N, M);
    sol += solve(M, N);
    cout << sol % MOD << endl;
    return 0;
}

Submission Info

Judge Result