← 返回题目列表

AtCoder · awtf2026algo_e

E. 偶数行

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

分数: 2500 点

问题陈述

有一块板 N 行和 M 列。 让我们呼叫位于 i从顶部开始的第行和 j左侧单元格中的第列 (i,j).

每个单元格都是空的或上面放置了一块。 董事会的状态由下式给出 N 长度-M 字符串 S_1,S_2,\ldots,S_N:如果 j- 第一个字符 S_{i} is .,细胞 (i,j) 为空,如果是 O,细胞 (i,j) 上面放置了一块。

对于整数 L 和 R (1 \leq L \leq R \leq N),定义 f(L,R) 如下。

  • 仅提取行 L 通过 R 板,获得板 R-L+1 行。称这个新板为 X.
  • 您可以重复以下操作 X 零次或多次。

    • 选择一个棋子并将其移动到与其相邻的任何单元格(上、下、左或右)。 这里,目标单元格上不能有其他块。 此外,您无法执行将棋子移出范围之外的操作 X.
  • 你的目标是达到这样的状态:对于每一行 X,该行的件数是偶数。 如果目标无法实现,那就让 f(L,R)=0。 如果可以的话,让 f(L,R) 是执行此操作所需的最少操作数。 每个输入的

查找 \sum_{1 \leq L \leq R \leq N} f(L,R),模数 998244353.

解决 T 例。

约束

  • 1 \leq T \leq 250000
  • 2 \leq N \leq 500000
  • 2 \leq M \leq 10
  • S_i 是一个长度为 M 组成 . 和 O.
  • 总和 N 超过 T 例最多 500000.

输入

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

T
case_1
case_2
\vdots
case_T

每个测试用例均按以下格式给出:

N M
S_1
S_2
\vdots
S_N

输出

对于每个测试用例,输出答案。


示例输入 1

7
3 2
O.
O.
.O
4 3
OOO
OOO
...
OOO
5 3
OOO
OOO
..O
OOO
...
7 3
OOO
..O
OOO
OOO
O..
OOO
.OO
8 3
OO.
OOO
OOO
..O
OOO
.O.
.OO
O..
4 5
.O..O
OOOOO
OOOOO
.O.O.
10 10
O.O..O..OO
........O.
OOO.O.OO.O
O..O..OOOO
OO..O.....
.OOOO..OO.
O.......O.
OOO.O.....
O.O.O....O
.....OO.O.

示例输出 1

3
5
9
7
29
9
44

的值 f(L,R) 第一个测试用例如下。

  • f(1,1)=0
  • f(1,2)=2
  • f(1,3)=0
  • f(2,2)=0
  • f(2,3)=1
  • f(3,3)=0