Colorings and Dominoes
Contest: Educational Codeforces Round 107 (Rated for Div. 2)
Difficulty rating: 2100
Tags: combinatorics, dp, greedy, math

You have a large rectangular board which is divided into $$$n \times m$$$ cells (the board has $$$n$$$ rows and $$$m$$$ columns). Each cell is either white or black.

You paint each white cell either red or blue. Obviously, the number of different ways to paint them is $$$2^w$$$, where $$$w$$$ is the number of white cells.

After painting the white cells of the board, you want to place the maximum number of dominoes on it, according to the following rules:

- each domino covers two adjacent cells;
- each cell is covered by at most one domino;
- if a domino is placed horizontally (it covers two adjacent cells in one of the rows), it should cover only red cells;
- if a domino is placed vertically (it covers two adjacent cells in one of the columns), it should cover only blue cells.

Let the value of the board be the maximum number of dominoes you can place. Calculate the sum of values of the board over all $$$2^w$$$ possible ways to paint it. Since it can be huge, print it modulo $$$998\,244\,353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$; $$$nm \le 3 \cdot 10^5$$$) — the number of rows and columns, respectively.

Then $$$n$$$ lines follow, each line contains a string of $$$m$$$ characters. The $$$j$$$-th character in the $$$i$$$-th string is * if the $$$j$$$-th cell in the $$$i$$$-th row is black; otherwise, that character is o.

Output format:
Print one integer — the sum of values of the board over all $$$2^w$$$ possible ways to paint it, taken modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3 4
**oo
oo*o
**oo

Example output:
144

Example input:
3 4
**oo
oo**
**oo

Example output:
48

Editorial:
There are different solutions to this problem involving combinatorics and/or dynamic programming, but, in my opinion, it's a bit easier to look at the problem from the perspective of probability theory.
Let's suppose a coloring is already chosen. Then it can be covered with dominoes greedily: red and blue cells are independent from each other, and, for example, red cells can be analyzed as a set of "strips" of them of different length. Let's say that we cover each "strip" from left to right, so, in each "strip", the first domino covers the cells $$$1$$$ and $$$2$$$, the second domino — the cells $$$3$$$ and $$$4$$$, and so on.
Let's calculate the average value of the coloring, that is, the expected value of the coloring if it is chosen randomly. Let it be $$$E$$$, then the answer is $$$2^w E$$$.
By linearity of expectation, $$$E$$$ can be calculated as $$$\sum\limits_{d \in D} p_d$$$, where $$$D$$$ is the set of all places we can use for a domino, and $$$p_d$$$ is the probability that there is a domino in place $$$d$$$ in our domino covering (which we construct greedily). Each domino covers two adjacent cells, so we can iterate on pairs of adjacent cells, and for each pair, find the probability that this pair is covered. Let's suppose that we want to cover the cells $$$(x, y)$$$ and $$$(x, y + 1)$$$ with a domino. Then:
• both of these cells should be red;
• the length of the red "strip" before these cells should be even (otherwise the cell $$$(x, y)$$$ will be paired with the cell $$$(x, y - 1)$$$).
The only thing we need to know in order to calculate the probability of these two conditions being true is the number of white cells before the cell $$$(x, y)$$$ — which can be easily maintained. Knowing the number of white cells before $$$(x, y)$$$, we can either use dynamic programming to calculate the required probability, or do the math on several easy examples and try to notice the pattern:
• if there are $$$0$$$ white cells before the current one, the probability of that pair being covered with a domino (let's call it $$$P_0$$$) is $$$\frac{1}{4}$$$ (both these cells should be red);
• if there is $$$1$$$ white cell before the current one, the probability of that pair being covered with a domino (let's call it $$$P_1$$$) is $$$\frac{1}{4} - \frac{1}{8}$$$ (the cells $$$(x, y)$$$ and $$$(x, y + 1)$$$ should be red, but the cell before them should not be red);
• $$$P_2$$$ is $$$\frac{1}{4} - \frac{1}{8} + \frac{1}{16}$$$ (either the chosen two cells are red and the cell before them is not red, or all four cells are red);
• $$$P_3$$$ is $$$\frac{1}{4} - \frac{1}{8} + \frac{1}{16} - \frac{1}{32}$$$, and so on.
So, knowing the number of white cells before $$$(x, y)$$$ and $$$(x, y + 1)$$$, we easily calculate the probability of this pair being covered by a domino. By summing up the probabilities over all pairs of adjacent white cells (don't forget the vertical ones!), we get the average (or expected) value of the coloring. All that's left is to multiply it by $$$2^w$$$.