【SGU】495.キッズand Prizes
892 ワード
http://acm.sgu.ru/problem.php?contest=0&problem=495
N個の箱M人は、最初のN個の箱にプレゼントがあります.M人は順に確率を待って箱を取ります.プレゼントがあれば、プレゼントを出して箱に戻します.プレゼントがなければ、操作しません.M人に贈り物の個数を出してほしいと聞きました.(N,M<=100000)
お母さんは意外にもQQを見ていい神様を見つけました.
このような補足の考えは神すぎます.答えはn-出されていない贈り物の個数の期待に等しいです.
M個人の操作は全部反発し合っていますので、毎回N個の箱の中から一つの箱を取ります.プレゼントに対して、選ばれない確率は((N-1)/N)^Mです.各権利値は全部1なので、N*1*((N-1)/N)^M)は贈り物の個数を選ばないという期待です.
いつもN個を望んでいますので、切ってもいいです.
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個を望んでいますので、切ってもいいです.