题目链接: http://vjudge.net/problem/viewProblem.action?id=42000
该过程为随即过程,因此总期望值等于个单词对应的期望值,即它们wasted的概率
#include <stdio.h>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath> using namespace std;
#define lson o<<1
#define rson o<<1|1
#define max(a,b) (a)>(b)?(a):(b)
#define min(a,b) (a)<(b)?(a):(b)
#define INF 200000000
#define N 100010
typedef long long ll;
long double lg[N]; void init (){
lg[]=;
for(int i=;i<N;i++){
lg[i]=(long double)log(i)+lg[i-];
}
}
int main(){
int n,k,cs=;
init();
while(scanf("%d%d",&n,&k) && n){
long double p,ans=;
int up,down,put=*k;
if(*k>n-)put=n-;
long double l0=lg[n-]-lg[n--put];
for(int i=;i<=n;i++){
up=max(i--k,);
down=max(n-i-k,);
if(up+down>=put)p=exp(lg[up+down]-lg[up+down-put]-l0);
else p=;
ans+=-p;
}
printf("Case %d: %.4lf\n",cs++,(double)ans);
}
return ;
}