AT2705 Yes or No(组合数学)

传送门

解题思路

　　首先将这个模型放到坐标轴上，\(x\)轴表示\(1\)，\(y\)轴表示\(0\)。问题就转化成了从\((0,0)\)走到\((n,m)\)，每次可以猜测向\(x\)轴或向\(y\)轴，而实际也有一条路线，求猜中的个数的期望。假设\(n<m\)首先如果一直猜\(m\)，答案必然为\(m\)，那么这是答案的下界。再考虑过\((n,m)\)做一条斜率为\(1\)的直线，如果在直线上，那么猜中的概率其实就为\(\frac{1}{2}\)。，而不在坐标轴上猜中的期望其实就为\(m\)。那么现在就是求走到直线的概率，根据期望的线性，可以考虑直线上每一个点产生的贡献，过这个点的路线就可以用组合数轻松算出了。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<cmath>using namespace std; const int N=1000005; const int MOD=998244353; typedef long long LL;int n,m,fac[N],inv[N]; int Ans1,Ans2;//LL gcd(LL x,LL y) { // if(!y) return x; // return gcd(y,x%y); //} // //struct Data{ // LL x,y; // Data(LL _x=0,LL _y=0) {x=_x; y=_y;} // friend Data operator+(const Data A,const Data B){ // Data ret; ret.y=A.y*B.y; ret.x=A.x*B.y+A.y*B.x; // LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp; // return ret; // } // friend Data operator*(const Data A,const Data B){ // Data ret; ret.x=A.x*B.x; ret.y=A.y*B.y; // LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp; // return ret; // } //}ans;inline int fast_pow(int x,int y){int ret=1;for(;y;y>>=1){if(y&1) ret=(LL)ret*x%MOD;x=(LL)x*x%MOD;}return ret; }inline int C(int x,int y){return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD; }int main(){scanf("%d%d",&n,&m);if(n>m) swap(n,m); fac[0]=inv[0]=1;for(int i=1;i<=n+m;i++) fac[i]=1ll*fac[i-1]*i%MOD;inv[n+m]=fast_pow(fac[n+m],MOD-2);for(int i=n+m-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD;Ans1=1ll*2*m*C(n+m,n)%MOD; Ans2=fast_pow(C(n+m,n)*2%MOD,MOD-2);for(int i=1;i<=n;i++) {Ans1=Ans1+1ll*C(n-i+m-i,n-i)*C(i+i,i)%MOD; Ans1%=MOD;}printf("%lld\n",1ll*Ans1*Ans2%MOD); // ans=ans+Data(1,2)*Data(C(n-i+m-i,n-i)*C(i+i,i),C(n+m,n)); // printf("%lld\n",1ll*ans.x*fast_pow(ans.y,MOD-2)%MOD);return 0; }

转载于:https://www.cnblogs.com/sdfzsyq/p/10396377.html

总结

以上是生活随笔为你收集整理的AT2705 Yes or No(组合数学)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。