分数: 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