luogu P1291 [SHOI2002]百事世界杯之旅

题目链接

题解

设\(f[k]\)表示还有\(k\)个球员没有收集到的概率

再买一瓶，买到的概率是\(k/n\)，买不到的概率是\((n-k) /k\)

那么\(f[k] = f[k]*(n-k)/n + f[k-1]*k/n + 1\)

移向一下\(f[k] = f[k-1] + n/k\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

inline int read()  {

    int x = 0,f = 1;

    char c = getchar();

    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}

    while(c <= '9' && c >='0') x = x * 10 + c - '0',c = getchar();

    return x*f;

}

#define LL long long

LL gcd(LL x,LL y) {return y == 0 ? x : gcd(y,x % y);}

int n;

int main() {

    n = read();

    LL fz = n, fm = 1,Tfz,Tfm;

    for(int i = 2;i <= n;++ i) {

        Tfz = n,Tfm = i;

        LL _gcd = gcd(Tfm,fm);

        fz = fz * (Tfm / _gcd) + Tfz * (fm / _gcd);

        fm *= (Tfm/_gcd);

        _gcd = gcd(fz,fm);

        fz /= _gcd,fm /= _gcd;

    }

    if(fm == 1) {printf("%lld",fz);return 0;}

    LL x = fz / fm;fz %= fm;

    LL tx = x,cnt=0;

    while(tx) cnt ++,tx /= 10;

    for(int i = 1;i <= cnt;++ i) printf(" ");

    printf("%lld\n",fz);

    if(x) printf("%lld",x);

    tx = fm;

    while(tx) printf("-"),tx /= 10; printf("\n");

    for(int i = 1;i <= cnt;++ i) printf(" ");

    printf("%lld",fm);

    return 0;

}

巴特西

luogu P1291 [SHOI2002]百事世界杯之旅

题目链接

题解

代码

最新文章

热门文章