zl程序教程

您现在的位置是:首页 >  其它

当前栏目

【SGU】495. Kids and Prizes

and
2023-09-27 14:22:21 时间

http://acm.sgu.ru/problem.php?contest=0&problem=495

题意:N个箱子M个人,初始N个箱子都有一个礼物,M个人依次等概率取一个箱子,如果有礼物则拿出礼物放回盒子,如果没有礼物则不操作。问M个人拿出礼物个数的期望。(N,M<=100000)

#include <cstdio>
using namespace std;

double mpow(double a, int n) {
	double r=1;
	while(n) { if(n&1) r*=a; a*=a; n>>=1; }
	return r;
}
int main() {
	int n, m;
	while(~scanf("%d%d", &n, &m)) {
		printf("%.10f\n", (double)n-(double)n*mpow((double)(n-1)/n, m));
	}
	return 0;
}

  

妈呀没想到只好看题解QAQ发现好神...

这种补集的想法太神了...答案可以等于n-没有被拿出的礼物个数的期望

由于M个人的操作都是互斥的,每一次均为在N个盒子里取1个盒子,那么对于每一个礼物,不被选到的概率是((N-1)/N)^M,由于每一个的权值都是1,所以N*1*((N-1)/N)^M)就是不被选中礼物个数的期望....

总期望是N个,因此剪掉即可....