题目链接
题解
设(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
",fz);
if(x) printf("%lld",x);
tx = fm;
while(tx) printf("-"),tx /= 10; printf("
");
for(int i = 1;i <= cnt;++ i) printf(" ");
printf("%lld",fm);
return 0;
}