“……在2002年6月之前购买的百事任何饮料的瓶盖上都会有一个百事球星的名字。只要凑齐所有百事球星的名字，就可参加百事世界杯之旅的抽奖活动，获得球星背包，随声听，更克赴日韩观看世界杯。还不赶快行动！”
你关上电视，心想：假设有n个不同的球星名字，每个名字出现的概率相同，平均需要买几瓶饮料才能凑齐所有的名字呢？
输入格式：
整数n（2≤n≤33），表示不同球星名字的个数。
输出格式：
输出凑齐所有的名字平均需要买的饮料瓶数。如果是一个整数，则直接输出，否则应该直接按照分数格式输出，例如五又二十分之三应该输出为（复制到记事本）： 5 \frac{3}{20}5203 第一行是分数部分的分子，第二行首先是整数部分，然后是由减号组成的分数线，第三行是分母。减号的个数应等于分母的为数。分子和分母的首位都与第一个减号对齐。
分数必须是不可约的。
难点大概是输出？
首先考虑一下抛开狗血输出怎么写吧。
设$f[n,k]$为在$n$个里面抽中了$k$个的期望购买量。
那么在手上有$(k-1)$个时，
那么$f[n,k]=f[n][k-1]+\frac{n}{n-k}$（抽中概率为$\frac{n-k}[n]$，期望为$1/p$）
所以递推就行了。
输出嘛，瞎几巴搞搞，问题也不大。
就是要注意UVA的输出比SHOI多了个空格QAQ肽毒了
1 /* 2 qwerta 3 P1291 [SHOI2002]百事世界杯之旅 Accepted 4 100 5 代码 C++，0.67KB 6 提交时间 2018-11-04 17:04:33 7 耗时/内存 30ms, 684KB 8 */ 9 #include<iostream> 10 #include<cstdio> 11 #include<cmath> 12 using namespace std; 13 #define LL long long 14 LL fz[37]; 15 LL fm[37]; 16 int main() 17 { 18 int n; 19 scanf("%d",&n); 20 fm[0]=1; 21 for(int k=1;k<=n;++k) 22 { 23 //f[n][k]=f[n][k-1]+n/(n-k+1); 24 fm[k]=fm[k-1]*(n-k+1); 25 fz[k]=fz[k-1]*(n-k+1)+fm[k-1]*n; 26 for(int j=2;j<=1e3;++j) 27 { 28 while(fm[k]%j==0&&fz[k]%j==0) 29 { 30 fm[k]/=j; 31 fz[k]/=j; 32 } 33 } 34 } 35 if(fz[n]%fm[n]==0){cout<<fz[n]/fm[n];return 0;} 36 int z=fz[n]/fm[n]; 37 fz[n]%=fm[n]; 38 for(int i=0;i<=log10(z);++i) 39 cout<<" "; 40 cout<<fz[n]; 41 cout<<endl; 42 cout<<z; 43 for(int i=0;i<=log10(fm[n]);++i) 44 cout<<"-"; 45 cout<<endl; 46 for(int i=0;i<=log10(z);++i) 47 cout<<" "; 48 cout<<fm[n]; 49 return 0; 50 }
转载于:https://www.cnblogs.com/qwerta/p/9905473.html
相关资源：JAVA上百实例源码以及开源项目