← 返回题目列表

Codeforces · 1237/F

F. 平衡多米诺骨牌放置

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

考虑一个方形网格,其中包含 $$$h$$$ 行和 $$$w$$$ 列,上面有一些多米诺骨牌。每个多米诺骨牌正好覆盖网格中共享公共边的两个单元。每个单元格最多被一张多米诺骨牌覆盖。

如果没有行和列包含被两个不同的多米诺骨牌覆盖的一对单元格,我们称网格上的多米诺骨牌放置完全平衡。换句话说,每一行和每一列都可以不包含被覆盖的单元、一个被覆盖的单元或属于同一个多米诺骨牌的两个被覆盖的单元。

多米诺骨牌在网格上完美平衡地放置。找出在此网格上放置零个或更多额外多米诺骨牌以保持放置完美平衡的方法数。输出该数字对 $$$998\,244\,353$$$ 取模。

输入

第一行包含三个整数 $$$h$$$、$$$w$$$ 和 $$$n$$$ ($$$1 \le h, w \le 360​​0$$$; $$$0 \le n \le 2400$$$),表示网格的尺寸和已放置的多米诺骨牌的数量。行的编号从 $$$1$$$ 到 $$$h$$$,列的编号从 $$$1$$$ 到 $$$w$$$。

接下来的 $$$n$$$ 行包含四个整数 $$$r_{i, 1}, c_{i, 1}, r_{i, 2}, c_{i, 2}$$$ ($$$1 \le r_{i, 1} \le r_{i, 2} \le h$$$; $$$1 \le c_{i, 1} \le c_{i, 2} \le w$$$),表示第$$$i$$$个多米诺骨牌覆盖的单元格的行id和列id。单元格 $$$(r_{i, 1}, c_{i, 1})$$$ 和 $$$(r_{i, 2}, c_{i, 2})$$$ 是不同的并共享公共边。

给定的多米诺骨牌放置完全平衡。

输出

输出在网格上放置零个或多个额外多米诺骨牌以保持放置完美平衡的方法数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

5 7 2
3 1 3 2
4 4 4 5

输出 #1

8

输入 #2

5 4 2
1 2 2 2
4 3 4 4

输出 #2

1

输入 #3

23 42 0

输出 #3

102848351

注意

在第一个示例中,初始网格如下所示:

以下是放置零个或更多额外多米诺骨牌以保持放置完美平衡的 $$$8$$$ 方法:

在第二个示例中,初始网格如下所示:

这里不能放置额外的多米诺骨牌。