[P1291][SHOI2002] 百事世界杯之旅 (期望)

题意：给出 n 个数，取到每个数的概率相等，求取完所有的数的概率；

解法：期望；

1.期望；我们可以设 f[i] 表示已经取完了 i 个数的期望，接下来我们考虑如何从 f[i] 转移到 f[i+1] ；

取一次：有 1*(n-i)/n 的期望抽到不同的数；

......

取K次：有 K*[(i/n)^(K-1)]*(n-i)/n 的期望抽到不同的数；

那么就对以上的式子进行一个等比公式的求和以及错位相减（在其间可以把一些趋近于 0 的数给舍掉），所以就可以得到最终的取到剩下的数的期望：n/(n-i)；

所以这道题的答案就可以化简为：n*(1/1+1/2+1/3+...+1/n)；

附上代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

int n;
ll fz,fm;

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

int main()
{
    cin>>n;
    fz=fm=1;
    for(int i=2;i<=n;++i){
        fz=fz*i+fm;
        fm*=i;
        ll g=gcd(fz,fm);
        fz/=g,fm/=g;
    }
    if(n%fm==0) cout<<fz*(n/fm);
    else {
        ll len=0,l=0,zs;
        zs=n*fz/fm;
        fz*=n,fz%=fm;
        ll g=gcd(fz%fm,fm);
        fz/=g,fm/=g;
        ll x=zs;
        while(x){len++,x/=10;}
        for(int i=1;i<=len;++i) cout<<" ";
        cout<<fz<<endl<<zs;
        x=fm;
        while(x){l++,x/=10;}
        for(int i=1;i<=l;++i) cout<<"-";
        cout<<endl;
        for(int i=1;i<=len;++i) cout<<" ";
        cout<<fm;
    }
    return 0;
}

​