題目連結: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\n",nowfz) ;
40 if(x) printf("%lld",x) ;
41 xx = nowfm ;
42 while(xx) printf("-"), xx /= 10 ; printf("\n") ;
43 for(int i=1;i<=hh;i++) printf(" ") ; printf("%lld",nowfm) ;
44 return 0 ;
45 }