#P18444. Rolling For Days
Rolling For Days
Rolling For Days
在游戏 TFT 中,玩家需要从商店购买单位,组成强大的阵容来对抗其他玩家。商店只会刷新一星单位;三个相同的一星单位可以合成为对应的二星单位,三个相同的二星单位又可以合成为对应的三星单位。星级更高的单位显然更强。商店刷出的单位是随机的,而刷新需要花费金币,因此即使有很多金币,也可能始终刷不到想要的单位。

游戏中一个令人烦恼的例子(原题配图)。
作为一位有规划的玩家,你想知道,为了完成某个特定阵容,究竟需要刷新多少次。为此,先考虑下面的简化问题。
卡池中一共有 张牌,分为 种,其中第 种有 张。目标阵容需要第 种牌 张。
每次刷新,从卡池中当前剩余的所有牌中等概率随机抽出一张。
- 如果这种牌已经买够了(即已购买数量等于目标需要的数量),就立刻将这张牌放回卡池。
- 否则,买下这张牌,并将它从卡池中移除。
求买齐全部目标牌所需的刷新次数的期望,答案对 取模。尚未购买的牌仍在池中;不需要的牌被放回,不能将所有抽出的牌都视作永久移除。
形式化地,记 。可以证明,该期望能表示为不可约分数 ,其中 为整数且 。输出 ,即满足 且 的整数 。
输入格式
第一行两个整数 ,满足 ,,分别表示牌的总数和种类数。
第二行 个整数 ,满足 且 ,表示每种牌的数量。
第三行 个整数 ,满足 ,表示目标需要的数量。
输入只有一个测试实例。
输出格式
输出一个整数,表示所需刷新次数的期望对 取模的结果。
样例 1
2 2
1 1
1 1
2
样例 2
4 2
2 2
2 1
582309210
样例 3
1000 12
101 43 34 281 23 24 12 25 66 222 145 24
37 43 27 257 5 11 12 19 62 41 87 13
265294941