2024 年浙江预赛

思路

尾和公式 $\mathbb{E}T={\sum }_{k\ge 0}\mathrm{Pr}(T>k)$ 来自把T写成“是否超过k”的指示量之和；有放回独立抽取使避开r个编号的概率为(1-r/n)^k。

想法从哪来：停止事件是某一组两张都见过，而继续事件要求每组至少缺一张，先把这个逻辑写清，才不会误用无放回排列。对固定抽取次数k，指定若干编号始终缺失的概率是一个简单幂。继续事件可写成四种“从每组各缺一张”的并，再用容斥；重复缺失三个、四个编号时的系数要按交叠次数合并。算出继续概率后，与其逐个求停止在第k次的概率再乘k，不如直接对继续概率求和，所有项都变成几何级数。k=0应为一、k=1仍为一，是检查容斥系数与尾和起点最方便的两个边界。

原题是“有放回”抽取，不能使用随机排列次序统计；用尾和公式计算尚未停止的概率。