题解 UVA10288 【优惠券 Coupons】

节选自[vercont的洛谷日报](https://45475.blog.luogu.org/mathematical-expectation) ## 题目链接： https://www.luogu.org/problem/UVA10288 - 题意简叙： 每张彩票上有一个漂亮图案，图案一共n种，如果你集齐了这n种图案就可以~~召唤神龙~~兑换大奖。 现在请问，在理想（平均）情况下，你买多少张彩票才能获得大奖的？ $n\leq33$ ### 分析： 本题我们设已经有了k个图案 令 $$a=\frac{k}{n}$$ 设拿到一种新的图案需要t次。 则概率为： $$a^{t-1}(1-a)$$ 则平均需要（已提出了（1-a））: $$(1-a)(1+2a+3a^2+4a^3+5a^4+...)$$ 即为 $$E(1-a)$$ 而此时我们需要观察其和$E(a)$的关系： $$E(a)=a+2a^2+3a^3+4a^4+...=E-1-a-a^2-a^3...$$ 整理可得 $$E(1-a)=1+a+a^2+a^3=\frac{1}{1-a}$$ 然后代换一下 $$E(1-a)=\frac{n}{n-k}$$ 这样结论就显而易见了： 假设有k个图案在手，那么平均再买$\frac{n}{n-k}$ 次就可以再得到一种新的图案，故可得总次数为： $$(\frac{1}{n}+\frac{1}{n-1}+\frac{1}{n-2}+\frac{1}{n-3}+\frac{1}{2}+1)n$$