Problem:


Score : 300 points

Problem Statement

We have a grid of H rows and W columns of squares. The color of the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j}: the square is white if c_{i,j} is ., and black if c_{i,j} is #.

Consider doing the following operation:

Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.

You are given a positive integer K. How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.

Constraints

1 \leq H, W \leq 6

1 \leq K \leq HW

c_{i,j} is . or #.

Input

Input is given from Standard Input in the following format:

H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}

Output

Print an integer representing the number of choices of rows and columns satisfying the condition.

Sample Input 1

2 3 2
..#
###

Sample Output 1

5

Five choices below satisfy the condition.

The 1-st row and 1-st column

The 1-st row and 2-nd column

The 1-st row and 3-rd column

The 1-st and 2-nd column

The 3-rd column

Sample Input 2

2 3 4
..#
###

Sample Output 2

1

One choice, which is choosing nothing, satisfies the condition.

Sample Input 3

2 2 3
##
##

Sample Output 3

0

Sample Input 4

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

Sample Output 4

208



Sample input:
2 3 2
..#
###


Sample output:
5

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
# import re
import math
import itertools

def main():
    h, w, k = input_list()
    maze = []
    for H in range(h):
        maze.append(list(input()))

    ans = []
    a = 0
    all = 0
    for l in maze:
        a += l.count('#')
        all += l.count('#')
    ans.append(a)
    hash_list_H = []
    kumi = 0
    for H in range(h):
        if maze[H].count('#') == k:
            kumi += 1
        # hash_list_H.append(maze[H].count('#'))

    hash_list_W = []
    for W in range(w):
        a = 0
        for H in range(h):
            if maze[H][W] == '#':
                a += 1
        if a == k:
            kumi += 1
        hash_list_W.append(a)
    # kumi = hash_list_W.count(k) + hash_list_H.count(k)
    # if all == k:
    #     kumi += 1
    # for H in range(1, h+1):
    #     for c in itertools.combinations(hash_list_H, H):
    #         if all - sum(list(c)) == k:
    #             kumi += 1
    # for W in range(1, w+1):
    #     for c in itertools.combinations(hash_list_W, W):
    #         if all - sum(list(c)) == k:
    #             kumi += 1
    # print(kumi)
    ss = 0
    # for H in range(1, h+1):
    #     for W in range(1, w+1):
    #         for hc in itertools.combinations(hash_list_H, H):
    #             for wc in itertools.combinations(hash_list_W, W):
    #                 if all - (sum(hc) + sum(wc)) == k:
    #                     ss += 1
    # print(kumi+ss)
    r = 0
    done = []
    for H in range(h+1):
        for W in range(w+1):
            for hc in itertools.combinations(range(h), H):
                for wc in itertools.combinations(range(w), W):
                    if (hc, wc) in done:
                        continue
                    done.append((hc, wc))
                    if count(maze, hc, wc) == k:
                        r += 1
    print(r)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def count(mazes, hc, wc):
    hc = list(hc)
    wc = list(wc)
    r = 0
    for hi, row in enumerate(mazes):
        if hi in hc:
            continue
        for wi, m in enumerate(row):
            if wi in wc:
                continue
            if m == '#':
                r += 1
    return r

def input_list():
    return list(map(int, input().split()))

def input_list_str():
    return list(map(str, input().split()))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

def split(word): 
    return [int(char) for char in word]  

H, W, K = map(int, input().split())
C = []
for _ in range(H):
    buff = str(input())
    for i in range(W):
        if buff[i] == '#':
            C.append(1)
        else:
            C.append(0)

#C = [1 if i == '#' else 0 for i in C_]
C = np.array(C).reshape(H,W)

cnum = np.sum(C)

count = 0
if cnum < K:
    print(0)
    exit(0)
else:  # 全探索
    for h in range(2 ** H):
        for w in range(2 ** W):
            # '00111' みたいなのを作る
            wline = bin(w)[2:].zfill(W)
            wline = split(wline)  # split to lists
            wzero = split(''.zfill(W))
            hline = bin(h)[2:].zfill(H)
            hline = split(hline)  # split to lists
            
            HW = []
            for hlin in hline:
                if hlin:
                    HW.append(wline)
                else:
                    HW.append(wzero)
            HW = np.array(HW).reshape(H, W)
            cnew = np.sum(C * HW)
            
            if cnew == K:
                count += 1
            
print(count)

Submission status: Accepted

Solution code:
import pprint
import copy
import itertools as it
H, W, K = map(int, input().split())
M__ = []
M_ = []
M = []
for _ in range(H):
    M__.append(list(input()))
rows = []
for i in range(H):
    rows += list(it.combinations(range(H), i))
cols = []
for i in range(W):
    cols += list(it.combinations(range(W), i))

def fillrow(n):
    global M_
    M_[n] = ['x' for _ in range(W)]

def fillcol(n):
    global M
    for i in range(H):
        M[i][n] = 'x'

ans = 0
for row in rows:
    M_ = copy.deepcopy(M__)
    for v in row:
        fillrow(v)

    for col in cols:
        M = copy.deepcopy(M_)
        for v in col:
            fillcol(v)
        if sum([M[i].count('#') for i in range(H)]) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
c = [[0 for i in range(W)] for j in range(H)]
cnt = 0
ans = 0
for i in range(H):
    line = input()
    for j, l in enumerate(line):
        if l == '.':
            continue
        else:
            c[i][j] = 1
            cnt += 1
for i in range(1<<H):
    for j in range(1<<W):
        flags = [[0 for i in range(W)] for j in range(H)]
        for n in range(H):
            if i>>n & 1:
                for p in range(W):
                    flags[n][p] = 1
                    '''
                    if c[n][p] & flags[n][p] == 0:
                        res -= 1
                        flags[n][p] = 1
                    '''
        for m in range(W):
            if j>>m & 1:
                for q in range(H):
                    flags[q][m] = 1
                    '''
                    if c[q][m] & flags[q][m] == 0:
                        res -= 1
                        flags[q][m] = 1
                    '''
        res = 0
        for p in range(H):
            for q in range(W):
                if flags[p][q] == 0 and c[p][q] == 1:
                    res += 1
        if res == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
g=[[] for i in range(h)]
for i in range(h):
  s=input()
  g[i].append(s)

t=[[0 for i in range(w)] for j in range(h)]
c=0
for i in range(h):
  for j in range(w):
    t[i][j]=g[i][0][j]
    if g[i][0][j]=='#':
      c+=1
black=[]
for i in range(h):
  l=0
  for j in range(w):
    if t[i][j]=='#':
      l+=1
  black.append(t)
for i in range(w):
  l=0
  for j in range(h):
    if t[j][i]=='#':
      l+=1
  black.append(l)
ans=0
for i in range(2**(h+w)):
  count=0
  i=format(i,'b').rjust(h+w,'0')
  
  hl=[]
  wl=[]
  for j in range(h):
    if i[j]=='1':
      hl.append(j)
  for k in range(h,h+w):
    if i[k]=='1':
      wl.append(k-h)
  for i in range(h):
    for j in range(w):
      if i not in hl and j not in wl and t[i][j]=='#':
        count+=1

  if count==K:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
def main():
    h,w,k = tuple([int(t)for t in input().split()])

    a = [list(input()) for _ in [0]*h]

    ans = 0
    for i in range(h+1):
        for rcom in combinations(range(h),i):
            for j in range(w+1):
                for ccom in combinations(range(w),j):
                    s = 0
                    for x in range(h*w):
                        if x//w in rcom or x%w in ccom:
                            continue
                        if a[x//w][x%w] == '#':
                            s += 1
                    if s==k:
                        ans +=1
                

    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	H,W,K = inputMap()
	maps = []
	for i in range(H):
		s = inputStr()
		maps.append(s)

	ans = 0
	for i in range(2**H):
		iBin = bin(i)[2:]
		pl = ""
		for ttt in range(len(iBin), H):
			pl += "0"
		iBin = pl + iBin
		iBin = iBin[::-1]
		for j in range(2**W):
			jBin = bin(j)[2:]
			pl = ""
			for ttt in range(len(jBin), W):
				pl += "0"
			jBin = pl + jBin
			jBin = jBin[::-1]

			kuro = 0
			for iii,mapH in enumerate(maps):
				if iBin[iii] == "1":
					continue
				for jjj,mapW in enumerate(mapH):
					if jBin[jjj] == "1":
						continue
					if mapW == "#":
						kuro += 1
			if kuro == K:
				ans += 1
	print(ans)




#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
c = [list(input()) for i in range(h)]
#print(c[1])
sum=0
f=[0]*h
g=[0]*w
for i in range(0,h):
	f[i]=c[i].count("#")
	sum+=f[i]
#for i in range(0:h)
	#for j in range(0:w):
		#if c[i][j]=="#"
			#g[j]+=1
ans=0
for bit in range(1<<h+w):
	d=list(range(h)) #赤にならない列番号
	e=sum #各選び方での黒の数
	for j in range(h+w):
		if(bit>>j)&1:
			if j<h:
				d.remove(j)
				e-=f[j]
				#print(j,d,e)
			else:
				for l in d:
					if c[l][j-h]=="#":
						e-=1
	if e==k:
		ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H, W, K = map(int, readline().split())
grid = [list(readline().decode().rstrip()) for _ in range(H)]
black_cnt = 0
a = [0]*H
b = [0]*W
for i in range(H):
  for j in range(W):
    if grid[i][j] == '#':
      a[i] += 1
      b[j] += 1
      black_cnt += 1
if black_cnt < K:
  print(0)
  sys.exit()
erase_cnt = black_cnt-K
N = H+W
ans = 0
for bit in range(1 << N):
    cnt = 0
    tmp_a = []
    tmp_b = []
    for i in range(N):
        if (bit >> i) & 1:       
            if i < H:
                tmp_a.append(i)
                cnt += a[i]
            else:
                tmp_b.append(i-H)
                cnt += b[i-H]
    for j in range(len(tmp_a)) :
        for k in range(len(tmp_b)):
            if grid[tmp_a[j]][tmp_b[k]] == '#':
                 cnt -= 1
    if cnt == erase_cnt:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K= map(int, input().split())
board=[]

def judge(H_ex,W_ex):
    cp_array=copy.deepcopy(board)
    for i in range(H):
        for j in range(W):
            if H_ex&(2**i)!=0:
                cp_array[i][j]=2
    for j in range(W):
        for i in range(H):
            if W_ex&(2**j)!=0:
                cp_array[i][j]=2
    count=0
    for i in range(H):
        for j in range(W):
            if cp_array[i][j]==1:
                count+=1
    if count==K:
        return True
    else:
        return False


for i in range(H):
    input_str=input()
    board.append([])
    for j in range(W):
        v=0
        if input_str[j]=="#":
            v=1
        board[i].append(v)

H_cmb=2**H
W_cmb=2**W
count=0

for i in range(H_cmb):
    for j in range(W_cmb):
        if judge(i,j)==True:
            count+=1



print("{}".format(count))

Submission status: Accepted

Solution code:
import numpy as np

H, W, K = input().split(' ')
H = int(H)
W = int(W)
K = int(K)
c = [list(str(input())) for i in range(H)]
cnp = np.array(c)

countAll = np.count_nonzero(cnp == '#')
countH = []
countW = []
for i in range(H):
    countH.append(np.count_nonzero(cnp[i] == '#'))
for i in range(W):
    countW.append(np.count_nonzero(cnp[:, i] == '#'))

ans = 0
for i in range(2 ** H - 1):
    for j in range(2 ** W - 1):
        tmp = countAll
        tmp2 = []
        choiceH = format(i, '0' + str(H) + 'b')
        for m in range(len(choiceH)):
            if int(choiceH[m]):
                tmp -= countH[m]
                tmp2.append(m)
        choiceW = format(j, '0' + str(W) + 'b')
        for n in range(len(choiceW)):
            if int(choiceW[n]):
                tmp -= countW[n]
                for o in range(len(tmp2)):
                    if cnp[tmp2[o], n] == '#':
                        tmp += 1
        if tmp == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product, combinations
from copy import deepcopy


def main():
    H, W, K = (int(x) for x in input().split(" "))
    sqr = [list(input()) for _ in range(H)]
    # mask_sqr = deepcopy(sqr)
    cnt_black = sum([len([y for y in x if y == "#"]) for x in sqr])
    cnt_way = 0
    for h in range(H+1):
        for w in range(W+1):
            for h_cs in combinations(range(H), h):
                for w_cs in combinations(range(W), w):
                    mask_sqr = deepcopy(sqr)
                    cnt_masked = 0
                    if len(h_cs) == 0:
                        for w_c in w_cs:
                            for i in range(len(sqr)):
                                if mask_sqr[i][w_c] == "#":
                                    mask_sqr[i][w_c] = "r"
                                    cnt_masked += 1
                    elif len(w_cs) == 0:
                        for h_c in h_cs:
                            for i in range(len(sqr[h_c])):
                                if mask_sqr[h_c][i] == "#":
                                    mask_sqr[h_c][i] = "r"
                                    cnt_masked += 1

                    else:
                        for h_c in h_cs:
                            for w_c in w_cs:
                                for i in range(len(sqr[h_c])):
                                    if mask_sqr[h_c][i] == "#":
                                        mask_sqr[h_c][i] = "r"
                                        cnt_masked += 1
                                for i in range(len(sqr)):
                                    if mask_sqr[i][w_c] == "#":
                                        mask_sqr[i][w_c] = "r"
                                        cnt_masked += 1

                    if cnt_black-cnt_masked == K:
                        cnt_way += 1
    print(cnt_way)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
#li=np.array([int(i) for i in list('{:06b}'.format(i)])
#exit()
H,W,K=map(int, input().split()) 
B=[]
for i in range(H):
  B.append(list(input()))
for i in range(H):
  for j in range(W):
    if(B[i][j]=='.'):
      B[i][j]=1
    else:
      B[i][j]=0
B=np.array(B)      

HC=np.zeros(H)
WC=np.zeros(W)
#i行目を取り出し
for i in range(H):
  HC[i]=np.count_nonzero(B[i]==1)
#j列目を取り出し  
for j in range(W):
  WC[j]=np.count_nonzero(B[:,j]==1)
WC=np.argsort(WC)
HC=np.argsort(HC)
count=0
for i in range(2 ** H):
  BB=B.copy()
  for iii in range(H):
    if [int(ii) for ii in list('{:06b}'.format(i))][6-H:][iii]==1:
      BB[iii]=1
  for j in range(2 ** W):
    BBB=BB.copy()
    for jjj in range(W):
      if [int(jj) for jj in list('{:06b}'.format(j))][6-W:][jjj]==1:
        BBB[:,jjj]=1
    if np.count_nonzero(BBB==0)==K:
      count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, acos, asin, atan, sqrt, tan, cos, pi
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


mod = 10 ** 9 + 7



h, w, k = LI()
ans = 0
C = SR(h)
for hbit in range(2 ** h):
    for wbit in range(2 ** w):
        ret = 0
        for hi in range(h):
            for wi in range(w):
                if (hbit >> hi & 1) and (wbit >> wi & 1) and C[hi][wi] == "#":
                    ret += 1
        if ret == k:
            ans += 1



print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
lis =[]
for i in range(H):
    a =[]
    k = input()
    for j in range(W):
        if k[j]==".":
            lis.append(0)
        else:
            lis.append(1)
ans = 0
from itertools import product
import copy
one = list(product([False,True],repeat=H))
two = list(product([False,True],repeat=W))
for i in one:
    for j in two:
        target = copy.copy(lis)
        t = 0
        s = 0
        for k in i:

            if k == True:
                for l in range(W):
                    target[t+l] =0
            t += W
        for m in j:

            if m == True:
                for n in range(H):
                    target[s + n*W]=0
            s += 1
        if target.count(1) == K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
# store graph
graph = []
for h in range(H):
  graph.append(list(input()))

answer = 0
# check all possibilities
for choices in range(2 ** (W+H)):
  #copy graph
  graph_copy = [ [0]*W for i in range(H)]
  for r in range(H):
    for c in range(W):
      graph_copy[r][c] = graph[r][c] 
  #one possiblity
  selected_rows = []
  selected_cols = []
  for i in range(W+H):
    if ((choices >> i) & 1):
      #row chosen
      if (i < H):
        row = i
        selected_rows.append(row)
      #col chosen
      else:
        col = i - H
        selected_cols.append(col)
  #check if that possibility is right
  #1)paint red
  for row in selected_rows:
    for col in range(W):
      graph_copy[row][col] = "."
  for col in selected_cols:
    for row in range(H):
      graph_copy[row][col] = "."
  #2)count blacks
  count = 0
  for r in range(H):
    for c in range(W):
      if (graph_copy[r][c] == "#"):
        count += 1
  if (count == K):
    answer += 1
    
    
print(answer)

Submission status: Accepted

Solution code:
import itertools as it
h,w,k = map(int, input().split())
a,b,c,d = [],[],[],[]
for i in range(h):
    a.append(i)
for i in range(1,h+1):
    b += it.combinations(a,i)
for i in range(w):
    c.append(i)
for i in range(1,w+1):
    d += it.combinations(c,i)
board = [str(input()) for i in range(h)]
ans = 0
for i in b:
    for j in d:
        sh = 0
        for m in i:
            for l in j:
                if board[m][l] == '#':
                    sh += 1
        if sh == k:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

def color(c,h,w):
    if len(h) != 0:
        for i in h:
            for j in range(W):
                c[i][j] = 'R'

    if len(w) != 0:
        for i in w:
            for j in range(H):
                c[j][i] = 'R'

    return c

def cunt(c):
    tot = 0
    for i in range(H):
        for j in range(W):
            if c[i][j] == "#":
                tot+=1
    return tot

H,W,K = map(int, input().split())
c = []
for i in range(H):
    tmp = list(input())
    c.append(tmp)

ans = 0

for i in range(2 ** H):
    for j in range(2 ** W):
        h = []
        w = []
        for  k in range(H):
            if ((i>>k) & 1):
                h.append(k)
        for k in range(W):
            if ((j >> k) & 1):
                w.append(k)
        _copy = deepcopy(c)
        tmp = color(_copy,h,w)
        # for _tmp in tmp:
            # print(_tmp)
        _cunt = cunt(tmp)
        # print(_cunt)
        if _cunt == K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
c = [[0]*w for _ in range(h)] #[h][w]
for i in range(h):
    f = input()
    for j in range(w):
        if f[j]=='#':
            c[i][j]+=1
            
yoko = [0]*h
tate = [0]*w
for i in range(h):
    yoko[i]=sum(c[i])
    for j in range(w):
        tate[j]+=c[i][j]
aaa = sum(yoko)
if aaa==k:
    ans=1
    for i in range(h):
        if yoko[i]==0:
            ans*=2
    for j in range(w):
        if tate[j]==0:
            ans*=2
    print(ans)
    exit()
    
ans = 0
for i in range(2**h-1):
    for j in range(2**w-1):
        cnt=0
        check1=[]
        check2=[]
        for n in range(h):
            if (i>>n)&1:
                cnt+=yoko[n]
                check1.append(n)
        for m in range(w):
            if (j>>m)&1:
                cnt+=tate[m]
                check2.append(m)
        for n in check1:
            for m in check2:
                if c[n][m]==1:
                    cnt-=1
        if aaa-cnt==k:
            ans+=1
        

print(ans)

Submission status: Accepted

Solution code:
import copy
H, N, K = map(int, input().split())
a = []
for i in range(H):
    b = list(input())
    a.append(b)

cnt = 0
for i in range(2**N):
    ans = []
    for co in a:
        ans.append(copy.copy(co))
    for j in range(N):
        if((i >> j) & 1):
            for k in range(len(ans)):
                ans[k][j] = 'r'
    for l in range(2**H):
        ans2 = []
        for co2 in ans:
            ans2.append(copy.copy(co2))
        for n in range(H):
            if((l >> n) & 1):
                for m in range(len(ans[n])):
                    ans2[n][m] = 'r'
        temp = 0
        for o in range(len(ans2)):
            for p in range(len(ans2[o])):
                if(ans2[o][p] == '#'):
                    temp += 1
        if(temp == K):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
canvas = [input().strip() for _ in range(H)]

canvas_as_int = [int(s.replace('.','0').replace('#','1'), 2) for s in canvas]

column_masks = [[int(s) for s in f"{j:b}".zfill(H)] for j in range(2**H)]

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f

res = 0
for i in range(2**W):
    row_masked_canvas = [popcount(n&i) for n in canvas_as_int]
    blacks = [sum(c * r for c,r in zip(column_mask,row_masked_canvas)) for column_mask in column_masks]
    res += blacks.count(K)

print(res)

Submission status: Accepted

Solution code:
import copy
H,W,K = list(map(int, input().split()))
C = list(list(input()) for _ in range(H))
ans = 0
for i in range(2 ** H):
  tmp = copy.deepcopy(C)
  for j in range(H):
    if ((i >> j) & 1):
      pass
    else:
      tmp[j] = list("." * W)
  for k in range(2 ** W):
    tmp2 = copy.deepcopy(tmp)
    for l in range(W):
      if ((k >> l) & 1):   
        pass   
      else:
        for h in range(H):
          tmp2[h][l] = "."
    result = 0
    for m in range(H):
      result += tmp2[m].count("#")
    if result == K:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split())
c = list()
for _ in range(H):
    c.append(input())

combiH = list(product([False, True], repeat=H))
combiW = list(product([False, True], repeat=W))

BLACK = ''.join(c).count('#')

result = 0
for redH in combiH:
    for redW in combiW:
        redRemovedInOneLine = ''
        for h in range(H):
            if redH[h]:
                continue
            for w in range(W):
                if redW[w]:
                    continue
                redRemovedInOneLine += c[h][w]
        
        if redRemovedInOneLine.count('#') == K:
            result += 1


print(result)

Submission status: Accepted

Solution code:
import numpy as np
Z=[]
H,W,K=map(int,input().split())
for i in range(H):
    data=list(map(str,input().split()))
    date=list(data[0])
    Z.append(date)
S=0

for i in range(2**(H+W)) :
    A=np.array(Z)
    for j in range(H+W) :
        if i>>j & 1 :
            if j<=H-1 : 
                A[j,:]="?"
            else :
                A[:,j-H]="?"
    count=np.count_nonzero(A=="#")
    if count==K :
        S=S+1

print(S)

Submission status: Accepted

Solution code:

import itertools as it
import copy

def main():
    H, W, K = map(int, input().split())
    C = []
    for h in range(H):
        C.append(list(input()))
    
    ans = 0
    Hlist = []
    Wlist = []

    for i in range(H+1):
        Hlist += list(it.combinations([x for x in range(H)], i))

    for j in range(W+1):
        Wlist += list(it.combinations([y for y in range(W)], j))

    for hli, wli in it.product(Hlist, Wlist):
        Ccopy = copy.deepcopy(C)
        for h in hli:
            Ccopy[h] = [0]*W
        
        for l in range(len(Ccopy)):
            for w in wli:
                Ccopy[l][w] = 0
        
        num = 0
        for li in Ccopy:
            num+= li.count('#')

        if num == K:
            ans += 1
    
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 173: C - H and V
https://atcoder.jp/contests/abc173/tasks/abc173_c
"""

import copy


def count_black(cells):
    count = 0
    for col in cells:
        count += col.count('#')
    return count


def draw_red_and_count(cells, xs, ys):
    for x in xs:
        for col in cells:
            col[x] = '@'
    for y in ys:
        for i in range(len(cells[y])):
            cells[y][i] = '@'
    return count_black(cells)


def main():
    H, W, K = list(map(int, input().split()))
    cells = [[0 for j in range(W)] for i in range(H)]
    for x in range(H):
        Cs = list(input())
        for y in range(W):
            cells[x][y] = Cs[y]

    Xs = []
    for i in range(2 ** W):
        Xs.append([j for j in range(W) if (i >> j) & 1])
    Ys = []
    for i in range(2 ** H):
        Ys.append([j for j in range(H) if (i >> j) & 1])

    ans = 0
    for xs in Xs:
        for ys in Ys:
            black_count = draw_red_and_count(copy.deepcopy(cells), xs, ys)
            if black_count == K:
                ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import copy

h,w,k = map(int,input().split())
c = [list(input()) for _ in range(h)]

A = [0,1]
h1 = list(itertools.product(A, repeat=h))
w1 = list(itertools.product(A, repeat=w))

ans = 0

for i in h1:
    for j in w1:
        c1 = copy.deepcopy(c)
        for ii in range(h):
            if i[ii]:
                for jjj in range(w):
                    c1[ii][jjj] = '.'
        for jj in range(w):
            if j[jj]:
                for iii in range(h):
                    c1[iii][jj] = '.'

        tmp = 0
        for ii in range(h):
            for jj in range(w):
                if c1[ii][jj] == '#':
                    tmp += 1
        if tmp == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
a=[]
ans=0
c=0
for i in range(H):
  t=input()
  c+=t.count('#')
  a.append(list(t))
for i in range(H+1):
  for j in range(W+1):
    for h in itertools.combinations(list(range(H)),i):
      for w in itertools.combinations(list(range(W)),j):
        b=c
        for k in h:
          for m in range(W):
            if a[k][m]=='#':
              b-=1  
        for l in w:
          for n in range(H):
            if a[n][l]=='#':
              b-=1
        for k in h:
          for l in w:
            if a[k][l]=='#':
              b+=1
        if b==K:
          ans+=1
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int,input().split())
C = [list(input()) for i in range(H)]

import itertools, copy

#print(C)
ans = 0

for h in range(H+1):#H+1
    for w in range(W+1):#W+1
        #print(h,w)#行と列 n個選ぶ
        comb_h = list(itertools.combinations(list(range(H)), h))
        comb_w = list(itertools.combinations(list(range(W)), w))

        #comb_H = []if comb_h == [()]
        
        #print(list(comb_h),list(comb_w))
        for ch in comb_h:
            for cw in comb_w:
                C_ = copy.deepcopy(C)
                #print(ch,cw)
                for x in ch:
                    for i in range(W):
                        C_[x][i] = "R"
                for y in cw:
                    for i in range(H):
                        C_[i][y] = "R"
                        
                #print(C_)
                #print
                #for cccc in C_:
                #    print("".join(cccc))

                cnt = 0
                for x in range(H):
                    for y in range(W):
                        if C_[x][y] == "#":
                            cnt += 1
                            
                if cnt == K:
                    ans += 1
                    
                    

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

H,W,K = map(int, input().split())
graph = np.array([[1 if x == "#" else 0 for x in list(input()) ] for _ in range(H)])
count = 0
ans = 0
for i in range(2**H):
    mas = np.copy(graph)
    for h in range(H):
        if 1 & (i >> h) == 1:
            mas[h,:] = 0
    for j in range(2**W):
        mass = np.copy(mas)
        for w in range(W):
            if 1 & (j >> w):
                mass[:,w] = 0
        if mass.sum() == K:
            count += 1

print(count)