- 今天来尝试了几道数学期望相关的题，这是我认为比较有趣的一道题
- 这次不废话啦直接开始~
- 一句话题意：两个分别装有n个糖果的盒子，每次随机选一个盒子然后拿走一颗糖（选的概率分别是\(p\)和\((1-p)\)），直到有一次选了一个盒子打开之后发现没有糖果了，求另一个盒子糖果个数的期望值
- \(n<=2*10^5\)
嗯首先我们得知道期望的线性性质：\(E(X+Y)=E(X)+E(Y)\)
-
如果我们假设最后打开的是第一个盒子，那么第二个盒子的糖果个数其实可能有\(0~n\)个，如果已经知道了有\(i\)个的概率就好了，这样根据期望的线性性质答案就是把所有的\(i*P(i)\)加起来（当然还要考虑最后打开第二个盒子）
-
好的我们现在来具体考虑第二个盒子有\(i\)个糖果的情况，第二个盒子还有\(i\)个的话那么在这之前盒子一定被打开过了\(n+n-i=2n-i\)次（\(n\)次取第一个盒子，\(n-i\)次取第二个），这样一来概率就是\(C(2n-i,n)p^{n+1}(1-p)^{n-i}\)（因为在这之前取了\(n\)次第一个盒子，这次又取了一次）
-
然后每次枚举一下\(i\)对两种情况（最后打开第一个或第二个盒子）求个和是不是就可以了？
-
蓝鹅这样子在理论上是正确的，但是实际求的时候\(C(2n-i,n)\)可以挺大的，而\(p^{n+1}\)和\((1-p)^{n-i}\)会很小，直接算的话会有精度误差（当然如果你要写高精度我也不拦你~），而且这个误差应该会比较大，大概超出了题目的要求（我之前改进后过程用double好像都wa掉了…），那么怎么办呢？
-
紫书上关于这题介绍了一种取对数的处理方法，具体来说就是在算的过程中全部取对数（我这里是\(e\)为底啦…不过好像一般也都是这样），比如最后打开第一个盒子时第二个盒子有\(i\)个糖果的概率取\(e\)的对数就是\(v1(i)=ln(C(2n-i,n))+(n+1)ln(p)+(n-i)ln(1-p)\)啦（第二个盒子的情况同理），最后把答案加上\(i(e^{v1(i)}+e^{v2(i)})\)就好啦~
-
预处理阶乘的对数的时候注意可能会用到\(n\)的两倍
-
再具体的话就没什么好说的啦
-
还是存一下代码吧~
#include<cstdio> #include<cmath> typedef long double ldouble; const int N=200005; ldouble p,LogF[N<<1]; inline double getC(int n,int k) { return LogF[n]-LogF[k]-LogF[n-k]; } inline double solve(int n) { double ans=0.0; for(int i=0;i<=n;i++) { ldouble c=getC(2*n-i,n); ldouble v1=c+log(p)*(n+1)+log(1-p)*(n-i); ldouble v2=c+log(p)*(n-i)+log(1-p)*(n+1); ans+=i*(exp(v1)+exp(v2)); }return ans; } int main() { int n,kase=0;LogF[0]=0; for(int i=1;i<(N<<1);i++)LogF[i]=LogF[i-1]+log(i); while(scanf("%d%Lf",&n,&p)==2) printf("Case %d: %.6lf\n",++kase,solve(n)); return 0; }
如果有错欢迎指出~
撒椛~（雾）