AT_abc173_c [ABC173C] H and V

题目描述

有一个由 $H$ 行 $W$ 列组成的网格。第 $i$ 行第 $j$ 列的格子的颜色由字符 $c_{i,j}$ 给出，当 $c_{i,j}$ 为 . 时表示白色，为 # 时表示黑色。

现在要进行如下操作：

• 可以选择若干行（也可以一行都不选），再选择若干列（也可以一列都不选）。然后，将被选中的所有行和所有列中的格子全部涂成红色。

给定一个正整数 $K$，问有多少种选择行和列的方法，使得操作后网格中恰好剩下 $K$ 个黑色格子。这里，如果存在某一行或某一列只在其中一种选择中被选中，则认为这两种选择不同。

输入格式

输入按以下格式从标准输入读入。

$H$ $W$ $K$
$c_{1,1}c_{1,2}\ldots c_{1,W}$
$c_{2,1}c_{2,2}\ldots c_{2,W}$
$\vdots$
$c_{H,1}c_{H,2}\ldots c_{H,W}$

输出格式

输出满足条件的行和列的选择方法数。

输入输出样例 #1

输入 #1

2 3 2
..#
###

输出 #1

5

输入输出样例 #2

输入 #2

2 3 4
..#
###

输出 #2

1

输入输出样例 #3

输入 #3

2 2 3
##
##

输出 #3

0

输入输出样例 #4

输入 #4

6 6 8
..##..
.#..#.
#....#
######
#....#
#....#

输出 #4

208

说明/提示

限制条件

• $1 \leq H, W \leq 6$
• $1 \leq K \leq HW$
• $c_{i,j}$ 仅为 . 或 #

样例解释 1

以下 $5$ 种选择满足条件：

• 第 $1$ 行和第 $1$ 列
• 第 $1$ 行和第 $2$ 列
• 第 $1$ 行和第 $3$ 列
• 第 $1$ 列和第 $2$ 列
• 第 $3$ 列

样例解释 2

什么都不选这一种选择满足条件。

由 ChatGPT 4.1 翻译