百事世界杯之旅

· · 个人记录

百事世界杯之旅

设当前已经拥有 k 个瓶盖，p=k/n ， 则还需 t 次才能得到一个新瓶盖的概率为 (1-p)^{t-1}p

\therefore E=1+\sum^{n-1}_{k=1} \sum^{+\infty}_{t=1}(1-\frac{k}{n})(\frac{k}{n})^{t-1}\times t =1+\sum^{n-1}_{k=1}(1-\frac{k}{n})\sum^{+\infty}_{t=1}(\frac{k}{n})^{t-1}\times t

设

S_m=\sum_{t=1}^m(\frac{k}{n})^{t-1}\times t \therefore S_m=1+2(\frac{k}{n})+3(\frac{k}{n})^2+4(\frac{k}{n})^3+5(\frac{k}{n})^4+...+m(\frac{k}{n})^{m-1} \therefore (\frac{k}{n})S_m=(\frac{k}{n})+2(\frac{k}{n})^2+3(\frac{k}{n})^3+4(\frac{k}{n})^4+...+(m-1)(\frac{k}{n})^{m-1}+m(\frac{k}{n})^m \therefore (1-\frac{k}{n})S_m=[1+\frac{k}{n}+(\frac{k}{n})^2+(\frac{k}{n})^3+...+(\frac{k}{n})^{m-1}]-m(\frac{k}{n})^m =\frac{1-(\frac{k}{n})^m}{1-\frac{k}{n}}-m(\frac{k}{n})^m =\frac{n}{n-k}-(\frac{n}{n-k}+m)(\frac{k}{n})^m \therefore S_m=(\frac{n}{n-k})^2-\frac{n}{n-k}\times \frac{m+\frac{n}{n-k}}{(\frac{n}{k})^m} \lim_{m\rightarrow+\infty}S_m=(\frac{n}{n-k})^2-\frac{n}{n-k}\times \frac{1}{(\frac{n}{k})^m\times ln(\frac{n}{k})}=(\frac{n}{n-k})^2 \therefore \sum^{+\infty}_{k=1}(\frac{k}{n})^{t-1}\times t = (\frac{n}{n-k})^2 E=1+\sum^{n-1}_{k=1}(\frac{n-k}{n}\times \frac{n}{n-k}\times \frac{n}{n-k}) =1+\sum^{n-1}_{k=1}\frac{n}{n-k} =\sum^{n-1}_{k=0}\frac{n}{n-k} =n\times \sum^{n-1}_{k=0}\frac{1}{n-k}

因此，

E=n\sum^{n-1}_{k=0}\frac{1}{n-k} 
#include <cstdio>
#include <iostream>
using namespace std;

typedef long long ll;

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

struct Frac
{
    ll a,b,z;
    Frac(ll A=0,ll B=1):a(A),b(B){}
    Frac operator + (const Frac& x)
    const{
        ll C=b*x.b,D=a*x.b+x.a*b;
        ll g=gcd(max(C,D),min(C,D));
        return Frac(D/g,C/g);
    }
};
inline int Len(ll x)
{
    if(x==0)return 0;
    int l=0;
    while(x)
    {
        l++;
        x/=10;
    }
    return l;
}
int main()
{
    ll n;
    cin>>n;
    Frac E(0,1);
    for(int i=1;i<=n;i++)E=E+Frac(n,(ll)i);
    if(E.b==1LL)cout << E.a;
    else
    {
        ll C=E.a/E.b,A=E.a%E.b,B=E.b;
        int l1=Len(C),l2=Len(B);
        for(int i=1;i<=l1;i++)cout << " ";
        cout << A << endl;
        if(C != 0)cout << C;
        for(int i=1;i<=l2;i++)cout << '-';
        cout << endl;
        for(int i=1;i<=l1;i++)cout << " ";
        cout << B;
        //当 C=0 时的情况。 
    }
    return 0;
}