← 返回题目列表

AtCoder · keyence2020_f

F. 单色化

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

分数: 1100 点

问题陈述

我们有一个 H \times W 网格,其中每个方格在初始状态下都被漆成白色或黑色。 给定的是字符串 A_1, A_2, ..., A_H 代表初始状态下方块的颜色。 对于每对 (i, j) (1 \leq i \leq H, 1 \leq j \leq W),如果 j- 第一个字符 A_i is .,位于 i第行和 j第-列被漆成白色;如果该字符是 #,该方块被漆成黑色。

其中 2^{HW} 将网格中的每个方格涂成白色或黑色的方法,通过以任意顺序执行任意次数(可能为零)的以下操作,从初始状态可以得到多少个?求这个计数的模数 998,244,353.

  • 选择一行,然后将该行中的所有方块涂成白色。
  • 选择一行,然后将该行中的所有方块涂成黑色。
  • 选择一列,然后将该列中的所有方块涂成白色。
  • 选择一列,然后将该列中的所有方块涂成黑色。

约束

  • 1 \leq H, W \leq 10
  • |A_i| = W (1 \leq i \leq H)
  • 所有字符串 A_i 包括 . 和 #.
  • H 和 W 是整数。

输入

输入由标准输入按以下格式给出:

H W
A_1
A_2
\vdots
A_H

输出

打印答案。


示例输入 1

2 2
#.
.#

示例输出 1

15

例如,如果我们将第二行涂成黑色,则网格变为:

#.
##

示例输入 2

3 3
...
...
...

示例输出 2

230

示例输入 3

2 4
#...
...#

示例输出 3

150

示例输入 4

6 7
.......
.......
.#.....
..#....
.#.#...
.......

示例输出 4

203949910