题目描述
“……在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 }