链接：https://ac.nowcoder.com/acm/problem/19777
来源：牛客网
题解
作者 岛田小雅
在这里先贴一下 OI Wiki 上期望的定义。
根据期望的定义和题意，我们可以这样去思考这道高中数学题：
令抽到第 \(1\) 张稀有卡是事件 \(X_1\)，我们令事件 \(Y_i\) 是抽第 \(i\) 张卡时能够抽到第 \(1\) 张稀有卡。很容易就能得出这个随机事件发生的概率 \(P(Y_i) = (\frac{N-M}{N})^{i-1}\times{\frac{M}{N}}\)。
那么事件 \(Y_i\) 的期望就是：
\[E(Y_i)=i\times{(\frac{N-M}{N})^{i-1}\times{\frac{M}{N}}} \]然后因为我们可以无限抽卡，那不妨设总共有 \(n\) \((n\to\infty)\) 种结果。
这样一来，根据期望的线性性，抽到第 \(1\) 张稀有卡的期望就是：
\[E(X_1) = \lim_{n\to{\infty}}\sum\limits_{i=1}^nE(Y)=\lim_{n\to{\infty}}\sum\limits_{i=1}^n(i\times(\frac{N-M}{N})^{i-1}\times{\frac{M}{N}}) \]那我们怎么算这个极限呢？首先翻开我们的高等数学上册……
\(\sum\) 这个符号对于初学者（比如我）来说比较不方便观察，我们可以把上面的式子展开成这样：
然后把 \(\frac{M}{N}\) 提出去：
\[E(X_1) = \frac{M}{N}\times\lim_{n\to{\infty}}(1\times(\frac{N-M}{N})^0+2\times(\frac{N-M}{N})^1+3\times(\frac{N-M}{N})^2+...+n\times(\frac{N-M}{N})^{n-1}) \]令
\[S=1\times(\frac{N-M}{N})^0+2\times(\frac{N-M}{N})^1+3\times(\frac{N-M}{N})^2+...+n\times(\frac{N-M}{N})^{n-1}\label{5}\\ \]那么
\[\frac{N-M}{N}\times{S}=1\times(\frac{N-M}{N})^1+2\times(\frac{N-M}{N})^2+3\times(\frac{N-M}{N})^3+...+n\times(\frac{N-M}{N})^n\label{6}\\ \]\((5)-(6)\) （错位相减法）得：
\[\frac{M}{N}\times{S}=(\frac{N-M}{N})^0+(\frac{N-M}{N})^1+(\frac{N-M}{N})^2+...+(\frac{N-M}{N})^{n-1}-(\frac{N-M}{N})^n \]\[S=\frac{N}{M}\times((\frac{N-M}{N})^0+(\frac{N-M}{N})^1+(\frac{N-M}{N})^2+...+(\frac{N-M}{N})^{n-1}-(\frac{N-M}{N})^n) \]所以：
\[E(X_1) = \lim_{n\to{\infty}}((\frac{N-M}{N})^0+(\frac{N-M}{N})^1+(\frac{N-M}{N})^2+...+(\frac{N-M}{N})^{n-1}-(\frac{N-M}{N})^n) \]好的然后我们把 lim(n->inf)(sum[((N-M)/N)^(i-1),{i,1,n}]-((N-M)/N)^n) 输入 Wolfram|Alpha 网站中就可以得到答案（啪）。
最终得到 \(E(X_1)=\frac{N}{M}\)。
接下来我们考虑抽第 \(2\) 张稀有卡的期望，这次事件 \(Y_i\) 的期望是：
\[E(Y_i)=i\times{(\frac{N-M}{N-1})^{i-1}\times{\frac{M-1}{N-1}}} \]同 \(E(X_1)\) 可得 \(E(X_2) = \frac{N-1}{M-1}\)。
同理可得 \(E(X_k)=\frac{N-K+1}{M-K+1}\)。
再根据期望的线性性，令抽到 \(K\) 张稀有卡为事件 \(Z\)。
\[E(Z)=\sum\limits_{i=1}^KE(X_i) \]\[E(Z)=\frac{N}{M}+\frac{N-1}{M-1}+...+\frac{N-K+1}{M-K+1} \]然后别化简了直接让计算机帮忙跑吧再算下去孩子死了。
AC 代码
作者 岛田小雅
#include <bits/stdc++.h>
using namespace std;
int t;
int n, m, k;
int cnt;
double ans;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << setiosflags(ios::fixed) << setprecision(7);
cin >> t;
while(++cnt <= t)
{
ans = 0;
cin >> n >> m >> k;
for(int i = 0; i < k; i++) ans += (double)(n-i)/(m-i);
cout << "Case #" << cnt << ": " << ans << '\n';
}
return 0;
}