CF1511E Colorings and Dominoes

你有一个被划分为 $n \times m$ 个格子的矩形大棋盘（棋盘有 $n$ 行 $m$ 列）。每个格子要么是白色，要么是黑色。 你需要将每一个白色格子涂成红色或蓝色。显然，不同的涂色方案共有 $2^w$ 种，其中 $w$ 是白色格子的数量。 在对棋盘上的白色格子涂色后，你希望在棋盘上放置尽可能多的多米诺骨牌，规则如下： - 每个多米诺骨牌覆盖两个相邻的格子； - 每个格子最多只能被一个多米诺骨牌覆盖； - 如果一个多米诺骨牌水平放置（即覆盖同一行的两个相邻格子），那么它只能覆盖红色格子； - 如果一个多米诺骨牌竖直放置（即覆盖同一列的两个相邻格子），那么它只能覆盖蓝色格子。 定义棋盘的价值为你能放置的多米诺骨牌的最大数量。请计算在所有 $2^w$ 种涂色方案下，棋盘价值的总和。由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3 \times 10^5$，$nm \le 3 \times 10^5$），表示棋盘的行数和列数。 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。第 $i$ 行的第 $j$ 个字符为 \* 表示该格子是黑色，否则为 o 表示该格子是白色。

输出一个整数，表示所有 $2^w$ 种涂色方案下棋盘价值的总和，对 $998\,244\,353$ 取模后的结果。

由 ChatGPT 4.1 翻译