【AGC019F】Yes or No

题目

题目链接：https://atcoder.jp/contests/agc019/tasks/agc019_f
有 (N+M) 个问题，其中有 (N) 个问题的答案是 YES，(M) 个问题的答案是 NO。当你回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。
答案对 (998244353) 取模。

思路

假设目前已经确定剩余 (n) 个 YES，(m) 个 NO，那么最优策略肯定是猜更多的那一边。
把选择 YES 看作是向左走一个单位长度，选择 NO 看作是向下走一个单位长度，那么这 (n+m) 个选择可以看作是从 ((n,m)) 走向 ((0,0)) 的一条路径。
对于一个点 ((x,y))，如果 (xgeq y)，那么就走到 ((x-1,y))，否则走到 ((x,y-1))。把每一个点到它下一步走的点的路径标记。那么对于这 (inom{n+m}{n}) 种答案的可能中任意一种，如果这一步走的是标记的路径，那么对的数量就 (+1)。
设 (ngeq m)，可以把直线 (f(x)=x) 左上方的网格直接翻折过来，发现每一条从 ((n,m)) 到 ((0,0)) 的路径，经过的标记边的数量就是 (n+) 走到直线 (f(x)=x) 且下一步往左的次数。
那么只需要对于直线 (f(x)=x) 的每一个点都求出有多少条路径会经过这一个点即可。组合数随便搞搞不难发现答案就是

[frac{sum^{m}_{i=1}inom{2i}{i}inom{n+m-2i}{n-i}}{inom{n+m}{n}}+n ]

时间复杂度 (O(n+m))。

代码

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

const int N=1000010,MOD=998244353,inv2=499122177;
int n,m;
ll ans,fac[N],inv[N];

ll fpow(ll x,ll k)
{
	ll ans=1;
	for (;k;k>>=1,x=x*x%MOD)
		if (k&1) ans=ans*x%MOD;
	return ans;
}

ll C(int n,int m)
{
	return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}

int main()
{
	scanf("%d%d",&n,&m);
	fac[0]=inv[0]=1;
	for (int i=1;i<=n+m;i++) fac[i]=fac[i-1]*i%MOD;
	inv[n+m]=fpow(fac[n+m],MOD-2);
	for (int i=n+m-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%MOD;
	if (n<m) swap(n,m);
	for (int i=1;i<=m;i++)
		ans=(ans+C(2*i,i)*C(n+m-2*i,n-i))%MOD;
	cout<<(ans*inv2%MOD*fpow(C(n+m,n),MOD-2)+n)%MOD;
	return 0;
}