#agc019f. [agc019_f]Yes or No
[agc019_f]Yes or No
问题陈述
你参加一场由 道题目组成的问答游戏,每道题目都有是/否的答案。
已知事先有 道题的答案是"是", 道题的答案是"否",但是题目以随机顺序给出。
你对任何一个题目的正确答案一无所知。你一次回答一个题目,并在回答后立即得知正确答案。
假设你按照使你回答的正确答案的期望数量最大化的策略进行操作。
记这个期望数量为 ,其中 和 是互质的整数。取模数 。可以证明存在唯一的整数 ,满足 ,并且 模 ,并且它等于 模 ,其中 是 的模反元素。求 。
约束条件
- 和 都是整数。
部分得分
- 对于满足 且 的测试集,将获得 分。
输入
输入的格式如下:
输出
假设你按照最优策略回答题目,你可以回答正确的数量的期望表示为一个互质分数 。以模 的形式输出 。
示例输入 1
1 1
示例输出 1
499122178
有两道题目。你可能对第一道题目随机回答,有 的概率回答正确。然后,由于你知道第二道题目的答案与第一道题目的答案不同,你有 的概率回答正确。
你回答正确的期望数量是 / 。因此,,,(模 ),(再次以模 输出)。
示例输入 2
2 2
示例输出 2
831870297
你回答正确的期望数量是 / 。
示例输入 3
3 4
示例输出 3
770074220
你回答正确的期望数量是 / 。
示例输入 4
10 10
示例输出 4
208827570
示例输入 5
42 23
示例输出 5
362936761