百事世界杯之旅[SHOI2002]

题目链接：https://www.luogu.org/problemnew/show/P1291

　题解：

　　其实问题可以看做集齐所以球星需要购买饮料数的期望值。

　　我们设fk表示还有k个球星未收集。这时再去买一瓶饮料抽到未收集过球星的概率为k/n，抽到收集过的球星的概率为（n-k）/n，那么fk = fk*（n-k）/n + fk-1*k/n + 1 ，移项可得 fk = fk-1 + n/k , 明显f0=0,那么我们只需通过上面的方程求出fn即可。

　　然后就是格式问题，认真读题就行了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define LL long long
 6 #define RI register int
 7 using namespace std;
 8 const int INF = 0x7ffffff ;
 9 const int N = 33 + 3 ;
10 
11 inline int read() {
12     int k = 0 , f = 1 ; char c = getchar() ;
13     for( ; !isdigit(c) ; c = getchar())
14       if(c == '-') f = -1 ;
15     for( ; isdigit(c) ; c = getchar())
16       k = k*10 + c-'0' ;
17     return k*f ;
18 }
19 int n ; 
20 
21 inline LL gcd(LL a,LL b) { if(a < b) swap(a,b) ; return !b ? a : gcd(b,a%b) ; }
22 int main() {
23     n = read() ; 
24     LL nowfz = n, nowfm = 1 ;
25     LL fz, fm ;
26     for(int i=2;i<=n;i++) {
27         fz = n, fm = i ;
28         LL gg = gcd(fm,nowfm) ;
29         nowfz = nowfz*(fm/gg) + fz*(nowfm/gg) ; nowfm *= (fm/gg) ;
30         gg = gcd(nowfz,nowfm) ;
31         nowfz /= gg, nowfm /= gg ;
32     }
33     if(nowfm == 1) {
34         printf("%lld",nowfz) ; return 0 ;
35     }
36     LL x = nowfz / nowfm ; nowfz %= nowfm ;
37     LL xx = x,hh = 0 ;
38     while(xx) hh++, xx /= 10 ;
39     for(int i=1;i<=hh;i++) printf(" ") ; printf("%lld
",nowfz) ;
40     if(x) printf("%lld",x) ;
41     xx = nowfm ;
42     while(xx) printf("-"), xx /= 10 ; printf("
") ;
43     for(int i=1;i<=hh;i++) printf(" ") ; printf("%lld",nowfm) ;
44     return 0 ;
45 }