← 返回题目列表

AtCoder · arc196_b

B. 环面环

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

分数: 700 点

问题陈述

有一个网格 H 行和 W 列。 行已编号 0,1,\ldots,H-1 从上到下,各列已编号 0,1,\ldots,W-1 从左到右。 让 (i,j) 表示行中的单元格 i 和专栏 j.

你被给予 H 字符串 S_0, S_1, \ldots, S_{H-1},每个长度 W 包括 A 和 B.

在每个单元格中,放置以下两种类型的图块之一。 让 S_{ij} 表示 (j+1)- 第一个字符 字符串的 (0 \le j \le W-1) 字符串的 S_i。放置在单元格中的图块类型 (i,j) is S_{ij}.

  • A 型:在瓷砖表面绘制一条线段,连接两个相邻边缘的中点。

  • B 型:在瓷砖表面绘制一条线段,连接两个相对边缘的中点。

这些图块可以自由旋转。当仅关注由线段形成的图案时,有四种旋转A型图块的方法和两种旋转B型图块的方法。因此,如果我们仅通过线段的图案来区分放置方式,则放置图块的方式有: 4^a \times 2^b,其中 a 是 A 型图块的数量, b 是 B 型图块的数量。

其中,打印数字,取模 998244353,当将网格视为圆环时,图块上的线段没有死角。

这里,“当将网格视为圆环时,图块上的线段没有死角”当且仅当每个单元格都满足以下两个条件时 (i,j):

  • 以下两者均存在,或以下均不存在:
    • 单元格中绘制的线段 (i,j),其端点是单元格右边缘的中点 (i,j)
    • 单元格中绘制的线段 (i,(j+1)\bmod W),其端点是单元格左边缘的中点 (i,(j+1)\bmod W)
  • 以下两者均存在,或以下均不存在:
    • 单元格中绘制的线段 (i,j),其端点是单元格下边缘的中点 (i,j)
    • 单元格中绘制的线段 ((i+1)\bmod H,j),其端点是单元格上边缘的中点 ((i+1)\bmod H,j)

例如,以下放置满足条件:

以下放置不满足条件。具体来说,虽然单元格中不存在端点为图块右边缘中点的线段 (0,2),有一条线段,其端点为单元格中图块左边缘的中点 (0,0),因此条件不满足。

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1 \le T \le 10^5
  • 2 \le H,W
  • HW\leq 10^6
  • S_i\,(0\le i\le H-1) 的长度-W 字符串组成 A 和 B.
  • 总和 H W 所有测试用例最多 10^6.
  • T, H,和 W 是整数。

输入

输入由标准输入按以下格式给出:

T
case_1
case_2
\vdots
case_T

每个案例均按以下格式给出:

H W
S_0
S_1
\vdots
S_{H-1}

输出

对于每个测试用例,打印数字,模数 998244353,满足条件的展示位置,位于单独的行中。


示例输入 1

3
3 3
AAB
AAB
BBB
3 3
BBA
ABA
AAB
3 4
BAAB
BABA
BBAA

示例输出 1

2
0
2

第一个测试用例的一个有效放置如下图所示: