首先容易发现最优策略是回答剩余多的选项。设 \(n\) 为剩余 Yes
的数量,\(m\) 为剩余 No
的数量,考虑将 \((n,m)\) 放到平面上,若 \(n > m\) 则回答 Yes
并向左走,\(n < m\) 则回答 No
并向下走,\(n=m\) 则随意。
如果按照这样的策略则至少能对 \(\max(n,m)\) 个,考虑计算 \(n=m\) 时能蒙对几个。
设当前在 \((i,i)\),经过 \((i,i)\) 的路径有 \(\binom{2i}{i} \times \binom{n-i+m-i}{n-i}\) 条,总路径有 \(\binom{n+m}{n}\) 条,则这部分的贡献为:
\[\dfrac{1}{2} \times \sum\limits_{i=1}^{min(n,m)} \dfrac{\binom{2i}{i} \times \binom{n-i+m-i}{n-i}}{\binom{n+m}{n}}
\]
加上 \(\max(n,m)\) 即为最终答案。
Code
// Problem: F - Yes or No
// Contest: AtCoder - AtCoder Grand Contest 019
// URL: https://atcoder.jp/contests/agc019/tasks/agc019_f
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 1000100;
const int N = 1000000;
const ll mod = 998244353;
const ll inv2 = (mod + 1) / 2;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, fac[maxn], ifac[maxn];
void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
ll ans = max(n, m), val = qpow(C(n + m, n) * 2 % mod, mod - 2);
for (int i = 1; i <= min(n, m); ++i) {
ans = (ans + C(i * 2, i) * C(n + m - i * 2, n - i) % mod * val % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- AtCoder Contest Grand 019 Yesatcoder contest grand 019 authentic atcoder contest grand negative atcoder contest grand atcoder contest grand 022 atcoder contest grand 001 histogram atcoder contest grand atcoder contest radius grand atcoder contest descent grand atcoder contest grand 017 atcoder contest grand 039