https://vjudge.net/problem/UVA-1639

题目

某人喜欢吃糖，有两个罐子，每个罐子都里装了n块糖，每天他都要随机打开一个罐子吃一块糖，概率分别为$p$，$1-p$，直到有一天，他打开罐子后发现这个罐子里面没有糖了。问另外一个罐子里剩下的糖的数量的期望是多少。

数据范围：$1\leqslant n\leqslant  2\times 10^5$

题解

以前看到这道题直接被吓到了，因为没有注意数据范围，所以直接就不去想枚举另外一个罐子里面剩下的糖的事情……

假设最后一次开的罐子是A，另外一个罐子剩余$k$个糖，那么概率是

\[p\cdot C(2n-k,n)(1-p)^{n-k}\cdot p^{n}\]

同理，若最后一次开的是B，另外一个罐子剩余$k$个糖，那么概率是

\[(1-p)\cdot C(2n-k,n)p^{n-k}\cdot (1-p)^{n}\]

所以期望就是

\[\sum_{k=0}^n k\times p\cdot C(2n-k,n)(1-p)^{n-k}\cdot p^{n}+\sum_{k=0}^n k\times (1-p)\cdot C(2n-k,n)p^{n-k}\cdot (1-p)^{n}\]

注意数据范围，因为数据变化比较大，计算的时候要注意尽量算同阶的，C可以达到$10^5!$，而p可以达到$10^{-6}^{10^5}$，都超出了double的范围，所以需要同时乘和除，比较麻烦……

另外一种办法是取对数，虽然很大，但是取了对数以后乘法变加法，$a*b^k$就会变成$k \ln(a+b)$，就不会超出范围，但是容易损失精度，题目要求的精度只有$10^{-4}$，因此也许可以使用这种方法……但是中间过程要用long double，直接double精度仍然过不了。

但是能降低编程复杂度，就算WA了一次也比调同时乘除快……

为了保险还是要练习码力啊，以后写个同时乘除的试下[快哭了]……

AC代码

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define REP(i,a,b) for(register int i=(a); i<(b); i++)
#define REPE(i,a,b) for(register int i=(a); i<=(b); i++)
#define PERE(i,a,b) for(register int i=(a); i>=(b); i--)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__)
#else
#define DBG(...) (void)0
#endif
#define ln log
using namespace std;
typedef long long LL;
int n;
long double p;
int kase=0;
long double jc[400007];
inline void db() {
	jc[0]=0;
	REP(i,1,400007) {
		jc[i]=jc[i-1]+ln(i);
	}
}
int main() {
	db();
	while(~scanf("%d%Lf", &n, &p)) {
		long double lnp = ln(p), ln1p=ln(1-p);
		long double ans=0;
		REPE(k,1,n) {
			ans+=k*exp(jc[2*n-k]-jc[n]-jc[n-k]+(n-k)*lnp+(n+1)*ln1p);
			ans+=k*exp(jc[2*n-k]-jc[n]-jc[n-k]+(n-k)*ln1p+(n+1)*lnp);
		}
		printf("Case %d: %.6Lf\n", ++kase, ans);
	}
	return 0;
}

UVA 1639 Candy

原文：https://www.cnblogs.com/sahdsg/p/11784322.html