https://atcoder.jp/contests/abc173/submissions/15023087

abc173_c_collect.py

from pprint import pprint
# pprint(C)
import sys
from collections import Counter
from itertools import product, combinations

H, W, K = map(int, input().split())

C = []
for _ in range(H):
    C.append(input())

counter = Counter()
for row in C:
    counter.update(row)
n_blacks = counter['#']

if n_blacks < K:
    print(0)
    sys.exit()

ans = 0
# mask_row, mask_col の場合
for mask_row in range(1<<H):
    for mask_col in range(1<<W):
        black = 0
        # ボード (i, j) がマスク対象でなく、かつ黒かどうかみたい
        # きちんとした行(列)マスクの作成とかは諦めて、ボードのマスを総当りする
        for i in range(H):
            for j in range(W):
                # (i, j) のボード状態は元のCを使った方がらく
                if (mask_row >> i & 1) == 0 and (mask_col >> j & 1) == 0 and (C[i][j] == '#'):
                    black += 1
        # print('{:b} {:b} {}'.format(mask_row, mask_col, black))
        if black == K:
            ans += 1
        # b = '{:b}'.format(masked_board)

print(ans)