提出 #73275734

---

ソースコード 拡げる

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll mod = 998244353;

ll modpow(ll a, ll b, ll m) {
	ll p = 1, q = a;
	for (int i = 0; i < 30; i++) {
		if ((b >> i) & 1) {
			p *= q;
			p %= m;
		}
		q *= q; q %= m;
	}
	return p;
}

ll divs(ll a, ll b, ll m) {
	return (a * modpow(b, m - 2, m)) % m;
}

ll ncr(ll n, ll r, vector<ll>& fact, vector<ll>& inv) {
	if (n < r || r < 0) return 0;
	return (fact[n] * inv[r] % mod) * inv[n - r] % mod;
}

ll narabekae(ll a, ll b, ll c, vector<ll> &fact, vector<ll> &inv) {
	return (fact[a + b + c] * inv[a] % mod) * (inv[b] * inv[c] % mod) % mod;
}

int main() {
	// step 1. input
	ll a, b, x, c; cin >> a >> b >> x >> c;

	// step 2. initialize
	vector<ll> fact(a + b + c + 1, 0);
	vector<ll> inv(a + b + c + 1, 0);
	fact[0] = 1;
	for (int i = 1; i <= a + b + c; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= a + b + c; i++) inv[i] = divs(1, fact[i], mod);

	// step 3. solve
	ll threshold = (2 * a + b) / (c + 1);
	ll sum = 0;
	for (int i = 0; i <= a; i++) {
		ll v = (threshold - 2 * i);
		for (int j = max(0LL, v - 1); j <= min(b, v + 2); j++) {
			ll score = 2 * i + j;
			if (score <= threshold) continue;

			// first case
			if (j >= 1 && score - 1 <= threshold) {
				ll way1 = narabekae(i, j - 1, 0, fact, inv);
				ll way2 = narabekae(a - i, b - j, c, fact, inv);
				ll way3 = narabekae(a, b, c, fact, inv);
				ll prob = divs(way1 * way2 % mod, way3, mod);
				sum += prob * score;
			}

			// second case
			if (i >= 1 && score - 2 <= threshold) {
				ll way1 = narabekae(i - 1, j, 0, fact, inv);
				ll way2 = narabekae(a - i, b - j, c, fact, inv);
				ll way3 = narabekae(a, b, c, fact, inv);
				ll prob = divs(way1 * way2 % mod, way3, mod);
				sum += prob * score;
			}
			sum %= mod;
		}
	}

	// step 4. output
	cout << sum << endl;
	return 0;
}

提出情報

ジャッジ結果