【SGU】495.キッズand Prizes

892 ワード

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
", (double)n-(double)n*mpow((double)(n-1)/n, m)); } return 0; }
  
お母さんは意外にもQQを見ていい神様を見つけました.
このような補足の考えは神すぎます.答えはn-出されていない贈り物の個数の期待に等しいです.
M個人の操作は全部反発し合っていますので、毎回N個の箱の中から一つの箱を取ります.プレゼントに対して、選ばれない確率は((N-1)/N)^Mです.各権利値は全部1なので、N*1*((N-1)/N)^M)は贈り物の個数を選ばないという期待です.
いつもN個を望んでいますので、切ってもいいです.