【集训队作业2018】购物 - 题目

按照剧本，fateicest 想要去买东西。而他自然要前往鸽巢去买东西。

鸽巢的商城是一个 $H \times W $ 的网格，西北角标号为 $(1, 1) $ ，东南角标号为 $(H, W) $ ，从北向南标号为 $1 \dots H $ ，从西向东标号为 $1 \dots W $ 。每个格子中都有一个商店，每家商店都会卖一样商品，不同的商店卖的商品互不相同。这个商城中划分出了 $n + 2 $ 个区域，作为功能区，我们将其标号为 $0 \dots n + 1 $ 。每个区域是一个矩形，第 $i $ 个矩形以 $(x_{l_{i}}, y_{l_{i}}) $ 为左上角， $(x_{r_{i}}, y_{r_{i}}) $ 为右下角。这 $n + 1 $ 个矩形满足下列条件：

$x_{l_{0}} \leq x_{r_{0}} < x_{l_{1}} \leq x_{r_{1}} < \dots < x_{l_{n + 1}} \leq x_{r_{n + 1}} $

$y_{l_{0}} \leq y_{r_{0}} < y_{l_{1}} \leq y_{r_{1}} < \dots < y_{l_{n + 1}} \leq y_{r_{n + 1}} $

其中，第 $0$ 个区域中的每个格子有一个传送门，可以把 fateicest 传入商场；第 $n + 1$ 个区域中每个格子，可以把 fateicest 传出商场；中间的第 $1$ 号到第 $n$ 号区域都是美食街，其中的每个格子都有一家餐馆。当然，这个商城的每个格子都很大，因此功能区并不影响格子里面有商店，即就算是功能区，格子里面依然是有商店的。注意到第 $0$ 号和第 $n + 1$ 号区域里面是没有餐馆的。

由于 fateicest 是个购物狂，因此他每经过一家商店，都会进去买一份那家商店的商品，包括起点和终点。如果他经过一家餐馆，他可以选择进去吃或是不进去吃。但是他非常想品尝这里的美食，因此他决定除 $0$ 号和 $n + 1$ 号以外的每个区域至少进一家餐馆。

fateicest 可以任选从第 $0$ 号区域的哪个格子进入商城，从第 $n + 1$ 号区域的哪个格子出去。他还可以任意选择走的路线。但因为他不想在这个商城花太多的时间，他只能向东或者向南走，即沿着一条最短路到出去的地方。

fateicest 想要知道，他在完成这次购物后，能有多少种不同的经历。两种经历是不同的当且仅当他买的东西集合不一样或者去的餐馆集合不一样。

fateicest 当然飞快地报出了答案，但是他想考考你。由于 fateicest 认为你不能像他那样飞快地报出答案，他只要你报出答案对 $998244353$ 取模后的结果就行了。

输入格式

从标准输入读入数据。

输入第一行两个整数 $H$ ， $W$ ，表示网格大小。

第二行一个整数 $n$ ，表示区域个数。

接下来 $n + 2$ 行，即第 $3$ 行到第 $n + 4$ 行，每行四个整数 $x_{l_{i}}$ ， $y_{l_{i}}$ ， $x_{r_{i}}$ ， $y_{r_{i}}$ ，表示一个区域的范围，第 $i$ 行表示第 $i - 3$ 个区域。

输出格式

输出到标准输出中。

输出一行一个整数，表示方案数对 $998244353$ 取模后的结果。

样例一

input

output

explanation

网格左上角长成这样：

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

其中他只能从 $0$ 入， $3$ 出，并且 $1$ 和 $2$ 都必须经过。因此从 $0$ 到 $1$ 有 $6$ 种方案，从 $1$ 到 $2$ 也有 $6$ 种方案，从 $2$ 到 $3$ 也有六种方案。一共是 $6^{3} = 216$ 种方案。

样例二

input

output

样例三

input

50 50
1
1 1 10 12
20 17 25 32
30 42 47 45

output

545916062

限制与约定

本题采用捆绑测试。

我们令 $A M X = max_{0 \leq i \leq n + 1} {max {x_{r_{i}} - x_{l_{i}} + 1, y_{r_{i}} - y_{l_{i}} + 1}}$

对于所有数据，满足：

$2 \leq H, W \leq 2 \times 10^{5}$
$0 \leq n \leq min {H, W} - 2$
对于 $\forall$ $0 \leq i \leq n + 1$ ，有 $1 \leq x_{l_{i}} \leq x_{r_{i}} \leq H, 1 \leq y_{l_{i}} \leq y_{r_{i}} \leq W$
对于 $\forall$ $0 \leq i \leq n$ ，有 $x_{r_{i}} < x_{l_{i + 1}}, y_{r_{i}} < y_{l_{i + 1}}$

共有 $9$ 个子任务，每个子任务的特殊限制和分值如下：

子任务编号	分值	$H, W$	$n$	$A M X$
1	2	$\leq 4$	——	——
2	5	$\leq 300$	$\leq 300$	——
3	11	$\leq 2 \times 10^{3}$	——	——
4	4	——	——	$= 1$
5	8	——	$= 0$	$\leq 10^{3}$
6	15	——	$= 0$	——
7	9	——	$= 1$	$\leq 10^{3}$
8	21	——	$= 1$	——
9	25	——	——	——

时间限制： $2s$

空间限制： $512MB$

下载

样例数据下载

Universal Online Judge

UOJ

#434. 【集训队作业2018】购物

输入格式

输出格式

样例一

input

output

explanation

样例二

input

output

样例三

input

output

限制与约定

下载