← 返回题目列表

Codeforces · 2240/B

B. 人工智能在这里什么也没找到

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

Milkcat2009 有一个矩阵 $$$a$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,由整数 $$$0$$$ 和 $$$1$$$ 组成。行的编号从 $$$1$$$ 到 $$$n$$$,列的编号从 $$$1$$$ 到 $$$m$$$。第 $$$i$$$ 行和 $$$j$$$ 列中的元素表示为 $$$a_{i,j}$$$。

Milkcat2009 的 AI 扫描由 $$$r$$$ 行和 $$$c$$$ 列组成的 $$$a$$$ 的每个子矩阵$$$^{\text{∗}}$$$。 AI 考虑矩阵 干净 如果每个此类子矩阵中元素的按位异或和等于 $$$0$$$。

形式上,矩阵 $$$a$$$ 有效当且仅当对于所有 $$$1 \le i \le n - r + 1$$$ 和 $$$1 \le j \le m - c + 1$$$: $$\bigoplus_{x=i}^{i+r-1} \bigoplus_{y=j}^{j+c-1} a_{x,y} = 0$$

其中 $$$\oplus$$$ 表示按位异或运算求和。

你的任务是,给定各种整数集 $$$n, m, r, c$$$,计算 干净 相对于扫描维度 $$$r$$$ 和 $$$c$$$ 的 $$$n$$$ 行和 $$$m$$$ 列矩阵。由于答案可能非常大,请以 $$$998\,244\,353$$$ 为模进行计算。

$$$^{\text{*}}$$$矩阵的子矩阵是通过从原始矩阵中删除一些行(从开头和/或结尾)和/或列(从开头和/或结尾)获得的。

输入

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

每个测试用例由一行包含四个整数 $$$n, m, r, c$$$ ($$$1 \le r \le n \le 10^9$$$, $$$1 \le c \le m \le 10^9$$$) 组成,分别代表矩阵的维度和扫描区域的维度。

输出

对于每个测试用例,输出一个表示答案模 $$$998\,244\,353$$$ 的整数。

示例

输入
复制

8
1 1 1 1
2 3 1 2
2 5 2 2
3 5 2 2
4 6 2 2
100 14 52 6
1000000000 1000000000 1000000000 1000000000
1000000000 1000000000 1 1

输出
复制

1
4
64
128
512
543661425
121099884
1

注意

对于第一个测试用例。唯一的元素 $$$a_{1,1}$$$ 必须满足 $$$a_{1,1} = 0$$$。由于 $$$a_{1,1}$$$ 必须是 $$$0$$$,因此只有 $$$1$$$ 有效矩阵:$$$[0]$$$。

对于第二个测试用例。条件要求每个 $$$1 \times 2$$$ 子矩阵的 XOR 和为 $$$0$$$。这意味着 $$$a_{i,j} \oplus a_{i,j+1} = 0$$$,因此对于所有有效的 $$$i,j$$$,$$$a_{i,j} = a_{i,j+1}$$$。对于每一行,所有元素必须相等。因此,每一行可以是 $$$[0, 0, 0]$$$ 或 $$$[1, 1, 1]$$$。对于 $$$2$$$ 行,有 $$$2^2 =4$$$ 有效矩阵。