E - Even Rows Editorial /

Time Limit: 5 sec / Memory Limit: 2048 MiB

配点 : 2500 点

問題文

N 行 M 列の盤面があります． 上から i 行目，左から j 列目のマスをマス (i,j) と呼ぶことにします．

各マスは空であるか，駒が 1 つ置かれているかのいずれかの状態です． 盤面の状態は N 個の長さ M の文字列 S_1,S_2,\ldots,S_N で与えられ，S_{i} の j 番目の文字が . ならばマス (i,j) は空で，O ならばマス (i,j) には駒が置かれています．

整数 L,R (1 \leq L \leq R \leq N) に対し，f(L,R) を以下のように定義します．

  • 盤面の L 行目から R 行目だけを取り出し，R-L+1 行からなる盤面を得る．この新しい盤面を X と呼ぶことにする．

  • あなたは X に対して以下の操作を 0 回以上繰り返すことができる．

    • 駒を 1 つ選び，それを四近傍のうち好きなマスに移動させる． ただし，移動先のマスに別の駒があってはいけない． また，駒が X の外に出るような操作もできない．

  • あなたの目標は，X のすべての行についてその行にある駒の個数が偶数である状態にすることである． 目標を達成することが不可能なら f(L,R)=0 とする． 可能なら，そのために必要な最小の操作回数を f(L,R) とする．

\sum_{1 \leq L \leq R \leq N} f(L,R) を 998244353 で割った余りを求めてください．

1 つの入力につき，T ケースを解いてください．

制約

  • 1 \leq T \leq 250000
  • 2 \leq N \leq 500000
  • 2 \leq M \leq 10
  • S_i は ., O からなる長さ M の文字列である
  • T ケースにわたる N の総和は 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

Score : 2500 points

Problem Statement

There is a board with N rows and M columns. Let us call the cell at the i-th row from the top and j-th column from the left cell (i,j).

Each cell is empty or has one piece placed on it. The state of the board is given by N length-M strings S_1,S_2,\ldots,S_N: if the j-th character of S_{i} is ., cell (i,j) is empty, and if it is O, cell (i,j) has a piece placed on it.

For integers L and R (1 \leq L \leq R \leq N), define f(L,R) as follows.

  • Extract only rows L through R of the board, obtaining a board with R-L+1 rows. Call this new board X.

  • You can repeat the following operation on X zero or more times.

    • Choose one piece and move it to any of the cells adjacent to it (up, down, left, or right). Here, the destination cell must not have another piece on it. Also, you cannot perform an operation that would move a piece outside of X.

  • Your goal is to reach a state where, for every row of X, the number of pieces in that row is even. If it is impossible to achieve the goal, let f(L,R)=0. If it is possible, let f(L,R) be the minimum number of operations required to do so.

Find \sum_{1 \leq L \leq R \leq N} f(L,R), modulo 998244353.

Solve T cases for each input.

Constraints

  • 1 \leq T \leq 250000
  • 2 \leq N \leq 500000
  • 2 \leq M \leq 10
  • S_i is a string of length M consisting of . and O.
  • The sum of N over the T cases is at most 500000.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each test case is given in the following format:

N M
S_1
S_2
\vdots
S_N

Output

For each test case, output the answer.

Sample Input 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.

Sample Output 1

3
5
9
7
29
9
44

The values of f(L,R) in the first test case are as follows.

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