#P18036. Ball Dumping Golf
Ball Dumping Golf
Ball Dumping Golf
题目描述
有 个盒子,编号为 。每个编号都有 个带有该编号的小球,共 个球。
将全部球打乱,放入这些盒子,使每个盒子恰好装有 个球。如果把所有球都视为可区分的个体,那么共有 种放置方式,每种方式等概率出现。特别地,同一编号的球在计算随机分布时仍视为不同个体。
你可以进行操作,每次操作包含以下步骤:
- 任选一个盒子,走到它面前。
- 如果当前盒子为空,本次操作结束。
- 否则,任选当前盒子里的一个球,将它丢弃。
- 走到编号等于刚刚丢弃的小球编号的盒子面前,返回步骤 2。
所有球都被丢弃时,所进行的操作次数就是得分。对于每一种初始放置方式,你都采取使得分最小的最优策略。
求这个最小得分的期望,对 取模。
期望可以写成最简分数 ,题目保证 不被 整除。需要输出唯一的整数 ,使 。
输入格式
一行两个整数 。
,。
输出格式
输出期望值对 取模的结果。
样例 1
输入:
2 2
输出:
166374060
样例 2
输入:
3 1
输出:
831870296
样例 3
输入:
100000 100
输出:
402978825
样例 1 中,最优得分为 2 的概率为 ,为 1 的概率为 ,期望为 。