题目描述

小美有很多组卡片，每个卡片上有一个值。现在他想随意取出两组卡片将他们混在一起，这时他会剔除值相同的卡片，将每个值相同的卡片只留下一张，现在他想知道他这个操作得到的新的一组卡片的个数的期望是多少。

思路：组合数学+贡献法计数

我们可以先去计算所有方案的总和，然后除以方案数$c$，即为最终的期望，其中$c=C(n,2)=\frac{n\times (n-1)}{2}$

我们可以考虑每一个元素对答案的贡献

对于元素$x$，记其在$n$组卡片出现的个数为$k$

• $k=1$，即只有一组卡片出现过，那么对答案的贡献为$n-1$