分数: 2000 点
问题陈述
您正在参加测验 N + M 问题和是/否答案。
事先已知有 N 问题及答案是和 M 问题的答案是“否”,但问题是按随机顺序提供给您的。
您不知道任何问题的正确答案。 你一一回答问题,并且对于你回答的每一个问题,回答后你立即就知道正确答案。
假设您遵循一种策略,最大化您给出的正确答案的预期数量。
令该预期数字为 P/Q,不可约分数。让 M = 998244353。 可以证明,有一个唯一的整数 R 之间 0 和 M - 1 存在使得 P = Q \times R 模数 M, 它等于 P \times Q^{-1} 模数 M,其中 Q^{-1} 是模逆 Q。 查找 R.
约束
- 1 \leq N, M \leq 500,000
- 两者 N 和 M 是整数。
部分分数
- 1500 通过满足以下条件的测试集将获得积分 N = M 和 1 \leq N, M \leq 10^5.
输入
输入由标准输入按以下格式给出:
N M
输出
让 P/Q 是您遵循最佳策略时给出的正确答案的预期数量,表示为不可约分数。 打印 P \times Q^{-1} 模数 998244353.
样本输入 1
1 1
示例输出 1
499122178
有两个问题。 你可以随机回答第一个问题,你有 50% 的概率会成功。 然后,由于您知道第二个答案与第一个答案不同,因此您将以 100% 的概率成功。
您的正确答案的预期数量是 3 / 2。 因此, P = 3, Q = 2, Q^{-1} = 499122177 (模数 998244353),以及 P \times Q^{-1} = 499122178 (再次,模 998244353).
示例输入 2
2 2
示例输出 2
831870297
您的正确答案的预期数量是 17 / 6.
示例输入 3
3 4
示例输出 3
770074220
您的正确答案的预期数量是 169 / 35.
示例输入 4
10 10
示例输出 4
208827570
示例输入 5
42 23
示例输出 5
362936761