AtCoder Regular Contest 114
E
Paper Cutting 2
AtCoder
⌀ 2514
原题
← DF →
翻译中…

Problem Statement

翻译中…

We have a rectangular piece of paper divided into $H \times W$ squares, where two of those squares are painted black and the rest are painted white. If we let $(i, j)$ denote the square at the $i$-th row and $j$-th column, the squares painted black are $(h_1, w_1)$ and $(h_2, w_2)$.

翻译中…

Maroon will repeat the following operation to cut the piece of paper:

翻译中…
  • Assume that we have $h \times w$ squares remaining. There are $(h - 1)$ horizontal lines and $(w - 1)$ vertical lines that are parallel to the edges of the piece and pass the borders of the squares. He chooses one of these lines uniformly at random and cuts the piece into two along that line. Then,
  • if the two black squares are on the same piece, he throws away the other piece and continues the process;
    • otherwise, he ends the process.
翻译中…

Find the expected value of the number of times Maroon cuts a piece of paper until he ends the process, modulo $998244353$.

翻译中…

Note

翻译中…

We can prove that the expected value in question is always a rational number. Additionally, under the constraints of this problem, we can also prove that if we express that value as an irreducible fraction $\frac{P}{Q}$, we have $Q \not \equiv 0 \pmod{998244353}$. Thus, there exists a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$. Answer this $R$.

翻译中…

Constraints

翻译中…
  • $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)$
  • All values in input are integers.
翻译中…

Input

翻译中…

Input is given from Standard Input in the following format:

翻译中…

H W
h_1 w_1 h_2 w_2

翻译中…

Print

翻译中…

Find the expected value of the number of times Maroon cuts a piece of paper until he ends the process, modulo $998244353$.

翻译中…

样例

Input #1
2 3
2 2 1 1
Output #1
332748119
In the first cut, the process will end with probability $2/3$. For the remaining case with probability $1/3$, the process will end in the second cut. Thus, the expected number of cuts is $1 \times 2/3 + 2 \times 1/3 = 4/3$.
Input #2
1 5
1 2 1 3
Output #2
332748120
Input #3
2 1
2 1 1 1
Output #3
1
The process will always end in the first cut.
Input #4
10 10
3 4 5 6
Output #4
831078040
题目信息
题号
arc114_e
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。