← 返回题目列表

Codeforces · 1511/E

E. 着色和多米诺骨牌

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

你有一个大的矩形板,它分为 $$$n \times m$$$ 个单元格(板有 $$$n$$$ 行和 $$$m$$$ 列)。每个单元格要么是白色的,要么是黑色的。

将每个白色单元格涂成红色或蓝色。显然,绘制它们的不同方式的数量为$$$2^w$$$,其中$$$w$$$是白色单元格的数量。

绘制板上的白色单元格后,您要根据以下规则在其上放置最大数量的多米诺骨牌:

- 每个多米诺骨牌覆盖两个相邻的单元格;
- 每个单元最多被一个多米诺骨牌覆盖;
- 如果多米诺骨牌水平放置(它覆盖其中一行中的两个相邻单元格),它应该只覆盖红色单元格;
- 如果多米诺骨牌垂直放置(它覆盖其中一列中的两个相邻单元格),它应该只覆盖蓝色单元格。

让棋盘的值为您可以放置​​的多米诺骨牌的最大数量。计算所有 $$$2^w$$$ 可能的绘制方法的板值总和。因为它可能很大,所以打印它对 $$$998\,244\,353$$$ 取模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$; $$$nm \le 3 \cdot 10^5$$$) — 分别是行数和列数。

接下来是 $$$n$$$ 行,每行包含 $$$m$$$ 个字符的字符串。如果第 $$$i$$$ 行中的第 $$$j$$$ 单元格为黑色,则第 $$$i$$$ 字符串中的第 $$$j$$$ 字符为 *;否则,该字符为 o。

输出

打印一个整数 — 棋盘上所有 $$$2^w$$$ 可能的绘制方式的值之和,以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3 4
**oo
oo*o
**oo

输出 #1

144

输入 #2

3 4
**oo
oo**
**oo

输出 #2

48

输入 #3

2 2
oo
o*

输出 #3

4

输入#4

1 4
oooo

输出#4

9