AGC019F Yes or No

题意

有 N+M 个问题，其中有 N 个问题的答案是 YES，M 个问题的答案是 NO

当回答一个问题之后，会知道这个问题的答案，求最优策略下期望对多少。

答案对 998244353 取模。

题解

首先可以想到 \(O(nm)\) 枚举分别剩下几个然后计算每一步的贡献

然后式子推不动，考虑一波实际意义

就是说第一象限有一张 \(n* m\) 的网格 (n>=m)，然后从 (0,0) 出发有一条斜率为 1 的射线

从 (n,m) 走到 (0,0)，若所在位置在射线左边会回答 NO，否则为 YES

而 \(m+n\choose n\) 种答案序列可以看成一些从 (n,m) 到 (0,0) 的折线

考虑每一条折线的贡献，发现在射线右边部分的贡献是向左走的步数，在射线左边的是向下走的步数，在射线上钦定为向左走的步数

然后可以将射线上的部分翻到射线下，答案是 n+刚好到射线上的点的概率* \(\frac{1}{2}\)

代码

#include
using namespace std;
#define il inline
#define int long long 
const int N=1e6+11;
const int mod=998244353;
int n,m,k;
int inv[N];
int jc[N],ny[N];
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
int C(int x,int y){
	if(y<0||x>=1,x=x*x%mod){
		if(y&1)s=s*x%mod;
	}return s;
}
void pre(){
	inv[0]=inv[1]=1;
	ny[0]=jc[0]=1;
	for(int i=1;i