CF1096E The Top Scorer

发表于 分类于 ， ， 阅读次数：

题意：共有 张卡牌，每张卡牌上都有一个非负整数。

这些牌之中数字最大的被称为王牌，若有多个最大数字，则随机选取一个。

现在，已知第一张牌上写的数 ，且各张牌上数字总和为 ，求第一张牌为王牌的概率。

结果对 取模，，，时限。

  • 若不考虑王牌的选择，这是个古典概型，可以考虑方案数处理。

  • 选王牌时，候选牌的个数不定，故不能用方案数的处理。

将选王牌的过程等价得改为：若最终有 的最大值，则每个最大值获得有 的收益，求第一张牌获得收益的期望。这样就回到古典概型。

先计算一下（不包括选择王牌）的总方案数。

个球，放入 个有标号盒子中，方案数为 。

再求第一张牌为王牌的方案的贡献和。

  • 子问题： 个数和为 且最大值 的方案数。

    考虑容斥，枚举钦定几个数超过限制，答案是 设为 。计算一次的复杂度为 。

首先枚举第一张牌的权值 ，再枚举最大值的个数 。贡献和为

复杂度为