#P8359. [ioi2018国家队集训]宝藏
[ioi2018国家队集训]宝藏
宝藏(treasure)
题目描述
有 个洞穴,宝藏位置在开始时从全部洞穴中等概率选定,之后保持不动。 每天可以派出 个机器人检测洞穴。机器人只有在检测宝藏所在洞穴时, 才以概率 找到宝藏;各次检测是否成功相互独立,且 。
你可以根据此前的未成功检测选择每天的搜索安排。求采用最优策略时, 首次找到宝藏的期望天数。第1天开始检测;当天至少一个机器人成功即视为找到。
概率 是有理数,且 与 互质。 输入中的字段 是 的标准代表元。 数据保证最优期望是有限有理数,且其最简分母与 互质。 若期望为最简分数 ,输出 。
输入格式
第一行一个整数 。 接下来 行,每行三个整数 。
输出格式
每组数据输出一行一个整数,表示期望天数的模值。
样例
6
1 1 500000004
2 1 500000004
3 2 500000004
1 1 333333336
2 1 333333336
3 2 333333336
2
500000007
777777786
3
500000009
866666677
数据范围
,,。 概率及期望还须满足题目描述中的可逆性保证。