链接
背景
\(UVA10288\)
题意
对于多组数据，每次给出 \(n\) 种卡片，每种抽出来的概率相同。求集齐 \(n\) 种卡片需要抽取的次数的期望。若答案不为整数请以带分数形式输出。第一行输出分子，第二行输出整数部分和分数线（中间以一个空格隔开），第三行输出分母。分数线的长度和分母相同，分子、分母、分数线需要左对齐。要求最终结果的分数部分不可约。
解法
整体过程显然是不好考虑的。不妨从其中的一小部分着手。假设当前已经抽出了 \(k\) 种卡片。则抽出还没有抽到过的卡片的概率为 \(\frac{n-k}{n}\) ，即 \(n\) 种可能结果中的 \(n-k\) 种要求的结果。根据概率与期望的关系，显然这一次抽到一种新卡的期望次数为 \(\frac{n}{n-k}\) 。则对于整个过程就是从 \(0\) 种卡抽到 \(1\) 种新卡，从 \(1\) 种卡抽到第 \(2\) 种新卡， \(\cdots \cdots\) 直到抽出第 \(n\) 种新卡。
因此总的期望次数就是 \(\sum_\limits{k \in [0,n)} \frac{n}{n-k}\) ，也即 \(\sum_\limits{k \in [1,n]} \frac{n}{k}\) 。 \(O(n)\) 计算即可。
为了以分数形式输出，需要分别处理分子分母，每次求和时就模拟分数相加的过程通分即可。
为了输出最简分数（同时避免分子（母）爆 \(long\) \(long\) ），需要边乘边约分（求最大公约数同除去即可）。
\(trick\)
一个非常用不经典套路：对于不便于计算的整体过程，不妨拆成很小的部分着手，观察变化，可窥知整体规律。
代码
$View$ $Code$
```cpp
#include
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>‘9‘||ch<‘0‘)
{
if(ch==‘-‘)
f=-1;
ch=getchar();
}
while(ch>=‘0‘&&ch<=‘9‘)
{
ret=(ret<<1)+(ret<<3)+ch-‘0‘;
ch=getchar();
}
return ret*f;
}
int n,len1,len2;
long long numerator,denominator;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
numerator=1ll;
denominator=1ll;
for(register int i=2;i<=n;i++)
{
numerator=numerator*i+denominator;
denominator*=i;
long long fac=gcd(numerator,denominator);
numerator/=fac;
denominator/=fac;
}
numerator*=n;
long long fac=gcd(numerator,denominator);
numerator/=fac;
denominator/=fac;
if(denominator==1)
printf("%lld\n",numerator);
else
{
long long integer=numerator/denominator,tmp=integer;
numerator-=denominator*integer;
len1=0;
while(tmp)
{
len1++;
tmp/=10;
}
for(register int i=0;i<=len1;i++)
printf(" ");
printf("%lld\n",numerator);
printf("%lld ",integer);
tmp=denominator;
len2=0;
while(tmp)
{
len2++;
tmp/=10;
}
for(register int i=1;i<=len2;i++)
printf("-");
printf("\n");
for(register int i=0;i<=len1;i++)
printf(" ");
printf("%lld\n",denominator);
}
}
return 0;
}
```
$UVA10288$ 优惠券 $Coupons$
原文：https://www.cnblogs.com/Peter0701/p/11743886.html
