zcmimi's blog
avatar
zc
2020-09-28 11:26:35
  • 本文总阅读量

查看原题

点击跳转

假设当前有了i个瓶盖,还差n-i个瓶盖

再买一个瓶盖在差的n-i个中的概率为\frac 1{n-i},

期望再买\dfrac n{n-i}次后拥有i+1个瓶盖

全部加起来就是\displaystyle \sum_{i=0}^{n-1} \frac n{n-i}

最终就是\displaystyle \left( \frac nn + \frac n{n-1}+\frac n{n-2}+\dots+\frac n1\right)

\frac xy+\frac ni=\frac {xi+yn}{yi}

#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int len(ll x){return log10(x)+1;}
void op(ll z,ll x,ll y){
    if(!x)return printf("%lld\n",z),void();
    for(int i=len(z);i;--i)putchar(' ');printf("%lld\n",x);
    printf("%lld",z);for(int i=len(y);i;--i)putchar('-');putchar('\n');
    for(int i=len(z);i;--i)putchar(' ');printf("%lld\n",y);
}
int main(){
    int n;scanf("%d",&n);
    ll x=0,y=1,k;
    for(int i=1;i<=n;++i){
        x=x*i+y*n,y=y*i;
        k=gcd(x,y),x/=k,y/=k;
    }
    op(x/y,x%y,y);
}
LG 1291 [SHOI2002]百事世界杯之旅
comment评论
Search
search