Submission #4575066

---

Source Code Expand

/*
AT2705 Yes or No
n为yes的题数，m为no的题数
当n>m的时候，猜yes
当n<m的时候，猜no
这样猜一定能保证猜对max(n,m)次
考虑n=m时猜对的期望
猜对的概率（对答案的贡献）是n/(n+m)=1/2
考虑走到(i,i)这个点的方案数
C(2i,i)*(n-i+m-i,n-i)
前2i步钦定i步向右走（剩余i步向上走）
后n-i+m-i步钦定n-i步向右走（剩余m-i步向上走），以免走出网格
故走到(i,i)的概率是sigma(C(2i,i)*(n-i+m-i,n-i))/C(n+m,n)
C(n+m,n)是总方案数 
当n=m时的期望贡献是(1/2)*sigma(C(2i,i)*(n-i+m-i,n-i))/C(n+m,n) i=1~min(n,m)
*/ 
#include <cstdio>
typedef long long ll;
#define ri register int
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast") 
const int N=1000005,mod=998244353;
int fac[N],inv[N];
inline int C(ri n,ri m){
	return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int max(ri x,ri y){
	return x>y ? x:y;
}
inline int min(ri x,ri y){
	return x<y ? x:y;
}
inline void add(int &x,ri y){
	x+=y;
	if(x>=mod) x-=mod;
}
inline int Pow(ri a,ri b){
	ri ans=1;
	for(;b;b>>=1,a=(ll)a*a%mod)
		if(b&1) ans=(ll)ans*a%mod;
	return ans;
}
int main(){
	ri n,m,i,sum,yes;
	scanf("%d%d",&n,&m);
	sum=n+m;
	fac[0]=inv[0]=1;
	for(i=1;i<=sum;++i) fac[i]=(ll)fac[i-1]*i%mod;
	inv[sum]=Pow(fac[sum],mod-2);
	for(i=sum-1;i;--i) inv[i]=(ll)inv[i+1]*(i+1)%mod;
	yes=0;
	for(i=min(n,m);i;--i) add(yes,(ll)C(2*i,i)*C(n-i+m-i,n-i)%mod);
	yes=(ll)yes*Pow(C(n+m,n),mod-2)%mod*inv[2]%mod;
	add(yes,max(n,m));
	printf("%d\n",yes);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^

Judge Result