← 返回题目列表

Codeforces · 1781/H2

H2. 窗口信号(硬版)

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

这是问题的困难版本。在此版本中,对 $$$h$$$ 和 $$$w$$$ 的约束更高。

海边的房子有 $$$h$$$ 层,高度相同。房子面向大海的一侧每层都有窗户,窗户之间的距离相等。因此,窗口位于大小为 $$$h \times w$$$ 的矩形网格的单元中。

在每个窗口中,除了给定的$$$k$$$(最多$$$2$$$)窗口之外,灯都可以打开或关闭。在这些 $$$k$$$ 窗户中,灯无法打开,因为它坏了。

在黑暗中,我们可以使用打开和关闭灯的配置向海上的船只发送信号。然而,船看不到灯相对于房屋的位置。因此,如果可以使用平行平移将开着灯的窗户的一种配置转换为另一种配置,则这些配置被认为是相等的。请注意,仅允许平行平移,但不允许旋转或翻转。此外,完全没有任何光的配置也不被认为是有效的。

找出船舶可以接收多少个不同的信号,并以 $$$998\,244\,353$$$ 为模打印该数字。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$h$$$、$$$w$$$ 和 $$$k$$$($$$1 \le h, w \le 200$$$; $$$0 \le k \le \min(h \cdot w, 2)$$$) - 房屋的高度、每层窗户的数量以及灯坏的窗户数量。

如果 $$$k > 0$$$,则接下来的 $$$k$$$ 行中的每一行都包含两个整数 $$$r_i$$$ 和 $$$c_i$$$($$$1 \le r_i \le h$$$; $$$1 \le c_i \le w$$$)— 楼层号和有破损灯的窗口号。楼层从下到上编号为 $$$1$$$ 到 $$$h$$$,窗户从左到右编号为 $$$1$$$ 到 $$$w$$$。如果 $$$k = 2$$$,则 $$$r_1 \ne r_2$$$ 或 $$$c_1 \ne c_2$$$。

保证所有测试用例的 $$$h \cdot w$$$ 总和不超过 $$$40\,000$$$。

输出

对于每个测试用例,打印一个整数 - 船舶可以接收的信号数量,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

10
1 3 0
2 2 0
3 2 0
4 5 0
12 7 0
1 1 1
1 1
1 3 1
1 2
3 4 1
3 4
2 3 2
1 1
2 1
4 5 2
2 3
4 2

输出 #1

4
10
44
954368
34903934
0
2
1696
10
253144

注意

在第一个测试用例中,船舶可以接收到四种不同的信号:所有灯亮;两个相邻窗户的灯亮着;最左边和最右边的窗户亮着;或在任何单个窗口中点亮。