分数: 700 点
问题陈述
我们有一张矩形纸,分为 H \times W 方块,其中两个方块被漆成黑色,其余的被漆成白色。如果我们让 (i, j) 表示位于 i第行和 j第列,涂成黑色的方块是 (h_1, w_1) 和 (h_2, w_2).
Maroon 将重复以下操作来切割纸张:
- 假设我们有
剩余 h \times w 格。有 (h - 1) 水平线和 (w - 1) 与图块边缘平行并穿过方块边界的垂直线。他均匀地随机选择其中一条线,然后沿着该线将这块作品切成两半。然后,
- 如果两个黑色方块在同一块上,则他扔掉另一块并继续该过程;
- 否则,他结束该过程。
求 Maroon 剪一张纸直到他结束进程的次数的期望值,取模 998244353.
注释
我们可以证明所讨论的期望值始终是有理数。另外,在这个问题的约束下,我们还可以证明,如果我们将该值表示为不可约分数 \frac{P}{Q},我们有 Q \not \equiv 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。回答这个 R.
约束
- 1 \leq H, W \leq 10^5
- H \times W \geq 2
- 1 \leq h_1, h_2 \leq H
- 1 \leq w_1, w_2 \leq W
- (h_1, w_1) \neq (h_2, w_2)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
H W h_1 w_1 h_2 w_2
打印
求 Maroon 剪一张纸直到他结束进程的次数的期望值,取模 998244353.
示例输入 1
2 3 2 2 1 1
示例输出 1
332748119
在第一次切割中,该过程将以概率结束 2/3。对于其余情况的概率 1/3,该过程将在第二次剪切时结束。
因此,预期的切割次数是 1 \times 2/3 + 2 \times 1/3 = 4/3.
示例输入 2
1 5 1 2 1 3
示例输出 2
332748120
示例输入 3
2 1 2 1 1 1
示例输出 3
1
该过程始终在第一次剪切时结束。
示例输入 4
10 10 3 4 5 6
示例输出 4
831078040