The 21st Hunan Provincial Collegiate Programming Contest——2025-湖南省赛-I. Tearing Paper

题目大意

题目描述

在一个 $n \times m$ 的网格平面上，有一个关键区域。该区域是一个闭矩形，其四个顶点的坐标分别为 $(a,b)$、$(a,d)$、$(c,d)$、$(c,b)$，其中 $0 \le a < c \le n$ 且 $0 \le b < d \le m$。

现在会随机选择一条从 $(0,0)$ 到 $(n,m)$ 的合法路径。合法路径是指每一步只能向右（$x$ 坐标加 $1$）或向上（$y$ 坐标加 $1$）的格点路径。

这条路径必定会将整个平面分成“左上”和“右下”两部分（允许其中一部分为空）。我们关注的是该关键区域是否会被这条路径切断。如果整个闭矩形区域完全位于路径的同一侧（完全在“左上”部分或完全在“右下”部分），则称该关键区域保持“完整”；否则视为被路径切断。

求在所有等概率选择的合法路径中，关键区域保持“完整”的概率。答案需要对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例的数量。

接下来每行代表一个测试用例，包含六个整数 $n, m, a, b, c, d$（$1 \le n \le 10^3$，$1 \le m \le 10^6$，$0 \le a < c \le n$，$0 \le b < d \le m$），其含义如题目描述所示。

输出格式

对于每个测试用例，单独输出一行一个整数，表示关键区域保持“完整”的概率对 $998244353$ 取模后的结果。

样例输入

3
3 3 1 1 2 2
3 3 0 0 3 3
3 3 0 1 3 2

样例输出

1
299473306
199648871

样例解释

在第一个测试用例中，关键区域的大小为 $1 \times 1$。它永远不会被任何路径切断，因此保持完整的概率为 $1$。

在第二个测试用例中，关键区域的大小为 $3 \times 3$，即覆盖了整个纸张。由于除非其中一部分为空，否则撕裂路径总是将纸张分成两个非空部分，因此关键区域保持完整的概率为 $\frac{2}{20}$，即 $\frac{1}{10}$。对 $998244353$ 取模后输出 $299473306$。

在第三个测试用例中，关键区域保持完整的概率为 $\frac{8}{20}$，即 $\frac{2}{5}$。对 $998244353$ 取模后输出 $199648871$。

思路讲解

完全理解隔板法（stars and bars）（插板法应用的特征）

我觉得是类似于这样子思考。

隔板法的思想就是，把 a 插入 d 个空格当中，换为给 a 加上 d-1 个隔板。

AC代码

源代码

心路历程（WA，TLE，MLE……）