← 返回题目列表

AtCoder · arc114_e

E. 剪纸2

中文机器翻译题面 查看原题

分数: 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