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: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split(",") for i in range(H)]
b=[]
d=[]
for i in range(len(c)):
  for item in c[i]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    b.append(item_mod)
  d.append(b)
  b=[]
  
d = [int(s) for s in d] 
C_arr = np.array(d)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertools.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split(",") for i in range(H)]
b=[]
d=[]
for i in range(len(c)):
  for item in c[i]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    b.append(item_mod)
  d.append(b)
  b=[]
  
d = [int(s) for s in d] 
C_arr = np.array(d)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split(",") for i in range(H)]
b=[]
d=[]
for i in range(len(c)):
  for item in c[i]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    b.append(item_mod)
  d.append(b)
  b=[]
 
 
C_arr = np.array(d)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
b=[]
d=[]
for i in range(len(c)):
  for item in c[i]:
    item_mod = item.replace("."  , "0")
    item_mod = item_mod.replace("#" , "1")
    b.append(item_mod)
  d.append(b)
  b=[]


C_arr = np.array(d)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
 
c.replace("." , 0)
c.replace("#" , 1)
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
 
c.replace("." , 0)
c.replace("#" , 1)
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
 
c.replace("." , 0)
c.replace("#" , 1)
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
 
c.replace("." , 0)
c.replace("#" , 1)
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [input().split() for i in range(H)]
 
c.replace("." , "0")
c.replace("#" , "1")
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append([input().replace(".","0").replace("#","1")])
    

C = int(C)
C_arr = np.array(C)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append([input().replace(".","0").replace("#","1")])

C_arr = np.array(C)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == K:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append([input().replace(".","0").replace("#","1")])

C_arr = np.array(C)

In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
C = []
for i in range(H):
    C.append((input().replace(".","0").replace("#","1")))

C_arr = np.array(C)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
 
H, W, K = list(map(int, input().split())) 
c = [list(input()) for i in range(H)]
 
c.replace("." , "0")
c.replace("#" , "1")
 
C_arr = np.array(c)
 
In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))
 
ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

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

c.replace("." , 0)
c.replace("#" , 1)

C_arr = np.array(c)

In = np.array(list(itertools.product([0,1] , repeat=H)))
Out = np.array(list(itertolls.product([0,1] , repeat=W)))

ans = 0
for i in range(2**H):
  for j in range(2**W):
    In_matrix = np.diag(In[i])
    Out_matrix = np.diag(Out[j])
    
    In_C = np.dot(In_matrix , C_arr)
    In_C_Out = np.dot(In_C , Out_matrix)
    
    ICO = In_C_Out.flatten()
    ICO = ICO.tolist()
    
    if ICO.count(1) == k:
      ans += 1
      
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,x=map(int,input().split())
P = [list( map( int, input().split() ) ) for i in range(n)]
ca=np.array(P).reshape((n,m+1))
value= 10000000
for i in range(2**n+1):
  sum=np.empty(m+1)
  for y in range(n):
    if (i >> y & 1) == 1:
      sum= sum + ca[-y,:]
  summ=sum[1:]
  if all(elm >= x for elm in summ) == True:
    value= min(int(sum[0]), value)
if value==10000000:
  print('-1')
else:
  print(value)

Submission status: Runtime Error

Solution code:
h, w, k = map(int, input().split())
arr = []
for i in range(0,h):
    arr.append(list(input()))
result = 0

num = 0
for i in range(0,h):
    num = 0
    for m in range(0,w):
        if arr[i][m] == "#":
            num +=1
        for j in range(0,i+1):
            for n in range(0,m+1):
                if arr[j][n] = '#':
                    num -= 1
        if num == k:
            result += 1
print(result)

Submission status: Runtime Error

Solution code:
h, w, k = map(int, input().split())
arr = []
for i in range(0,h):
    arr.append(list(input()))\
result = 0

num = 0
for i in range(0,h):
    num = 0
    for m in range(0,w):
        if arr[i][m] == "#":
            num +=1
        for j in range(0,i+1):
            for n in range(0,m+1):
                if arr[j][n] = '#':
                    num -= 1
        if num == k:
            result += 1
print(result)

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
C = [ input() for i in range(H)]
ans = 0
for i in range(1 << H):
    for j in range(1 << W):
        cnt = 0
        for m in range(H):
            for n in range(W):
                if ((i >> m) & 1): 
                    continue
                if ((j >> n) & 1): 
                    continue
                if C[m][n] == '#':
                    cnt += 1
        if cnt == K: 
            ans += 1
        elif cnt != K:
print(ans)

Submission status: Runtime Error

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

ans = 0
for i in range(H+1):
  for j in range(W+1):
    countRed = 0
    _board = board
    if i>0:
      for h in range(W):
        _board[i-1][h] = "."
    if j>0:
      for h in range(H):
        _board[h][j-1] = "."
      for h in range(H):
        countRed += board[h].count("#")
    if countRed == K:
      ans += 1
 
print(correct)

Submission status: Runtime Error

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

correct = 0
for i in range(H+1):
  for j in range(W+1):
    countRed = 0
    _board = board
    if i>0:
      for h in range(W):
        _board[i-1][h] = "."
    if j>0:
      for h in range(H):
        _board[h][j-1] = "."
        countRed += board[h].count("#")
    if countRed == K:
      correct += 1

print(correct)

Submission status: Runtime Error

Solution code:
H,W,k=rm()
a=[list(input()) for i in range(H)]
ans=0
for h in range(1<<H):
    for w in range(1<<W):
        count=0
        for i in range(H):
            for j in range(W):
                if (a[i][j]!='#'):
                    continue
                if h>>i&1!=0 or w>>j&1!=0:
                    continue
                count+=1
        if count==k:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
h, w, k = [int(i) for i in input().split()]
masu = [input() for _ in range(h)]
ans = 0
for mark_h in range(2**h):
    for mark_w in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (mark_h>>i)&1==1 and (mark_w>>j)&1==1:
                    if c[i][j]=="#":
                        black+=1
        if black=k:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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
A
H, W, K = LI()
c = SRL(H)

ans=0
 
for i in range(2**H):
    seen=[]
    for n in range(H):
        if ((i>>n) & 1):
            seen.append(c[n])
    for j in range(2**W):
        count=0
        for m in range(W):
            if ((j>>m) & 1):
                for l in range(len(seen)):
                    if seen[l][m]=="#":
                        count+=1

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

Submission status: Runtime Error

Solution code:
import sys
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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 = IR(3)
c = SRL(H)

ans=0
 
for i in range(2**H):
    seen=[]
    for n in range(H):
        if ((i>>n) & 1):
            seen.append(c[n])
    for j in range(2**W):
        count=0
        for m in range(W):
            if ((j>>m) & 1):
                for l in range(len(seen)):
                    if seen[l][m]=="#":
                        count+=1
]
        if count==K:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read

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

C = np.frombuffer(read(), dtype='S1').reshape(H, -1)

def f(x, y, C):
	rows = [i for i in range(H) if x & (1<<i)]
	cols = [i for i in range(W) if y & (1<<i)]
	D = C[rows][:, cols]
	return D.sum() == K

res = 0
for x in range(1<<H):
	for y in range(1<<W):
		res += f(x, y, C)
print(res)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
la=[list(input()) for _ in range(h)]
import itertools
import copy
res=0
p=range(h);q=range(w)
for v1,v2 in itertools.product(p,q):
    li=copy.copy(la)
    li[v1]="."
    for j in range(h):
        li[j][v2]="."
print(res)

Submission status: Runtime Error

Solution code:
h, w, k = map(int,input().split())
c = [list(input()) for i in range(h)]
ans = 0
for p_h in range(2**h):
    for p_w in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (p_h>>i)&1==0 and (p_w>>j)&==0:
                    if c[i][j]=='#':
                        black += 1
        if black == k:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
h, w, k = map(int, input().split())
c = [input(i) for i in range(h)]
ans = 0
for p_h in range(2**h):
    for p_w in range(2**w):
        black = 0
        for i in range(h):
            for j in range(w):
                if (p_h>>i)&1==0 and (p_w>>j)&1==0:
                    if c[i][j]=='#'
                        black +=1
        if black == k:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
h,w,k=map(int, input().split())
mat = []
for i in range(h):
  s = input()
  mat.append(s)
total = 0
for y in range(2**h):
  for x in range(2**w):
    mat2 = mat.copy()
    y_bin = bin(y)[2:]
    x_bin = bin(x)[2:]
    for r in y_bin:
      if r == "1":
        mat2[r] = "."*w
    for c in x_bin:
      if c == "1":
        for r in range(h):
          mat2[r][c] = "."
    count = 0
    for r in range(h):
      for c in range(w):
        if mat2[r][c] == "#":
          count += 1
    if count == k:
      total += 1
print(total)

Submission status: Runtime Error

Solution code:
from itertools import product
h,w,k=map(int,input().split())
idxs=[]
cols=[0]*w
al=0

def nir(x):
  if x=='#':return 1
  else:return 0
  
for _ in range(h):
  tmp=list(map(nir, list(input())))
  idxs.append(sum(tmp))
  al+=sum(tmp)
  for q in range(w):
    cols[q]+=tmp[q]
    
for bits in product((0,1),repeat=h+w):

Submission status: Runtime Error

Solution code:
H,W,K = list(map(int,input().split()))
c = []
for i in range(H):
    c.append(list(input()))
ans = 0
H_pattern,W_pattern = 2**H,2**W
for i in range(0,H_pattern):
    for j in range(0,W_pattern):
        H_active,W_active=list(bin(H_pattern,i)[2:].zfill(H)),list(bin(W_pattern,j).zfill(H))
        count = 0
        for k,arr in enumerate(c):
            for l,item in enumerate(arr):
                if H_active[k] == "1" and W_active[l] == "1" and item == "#":
                    count += 1
        if count == K:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from math import *
from cmath import rect

def dft(f,x):
  if len(f)==1:
    return
  f0,f1=f[0::2],f[1::2]
  dft(f0,x)
  dft(f1,x)
  z=rect(1,x*2*acos(-1)/len(f))
  n=1+0j
  for i in range(len(f)):
    f[i]=f0[i%len(f0)]+n*f1[i%len(f1)]
    n=n*z

def pm(p,q):
  siz=1
  while len(p)+len(q)>siz:
    siz*=2
  np=[]
  nq=[]
  for i in range(len(p)):
    np.append(rect(p[i],0))
  for i in range(len(q)):
    nq.append(rect(q[i],0))
  while len(np)<siz:
    np.append(0+0j)
  while len(nq)<siz:
    nq.append(0+0j)
  dft(np,1)
  dft(nq,1)
  for i in range(siz):
    np[i]=np[i]*nq[i]
  dft(np,-1)
  EPS=0.1
  for i in range(siz):
    np[i]=int(np[i].real/siz+EPS)
  return np

H,W,K=map(int,input().split())
C=[input() for i in range(H)]
DP=0
X=[]
P=0

def poly(x):
  r=[0]*x
  r.append(1)
  r[0]+=1
  return r

def knapsack(L):
  if len(L)==1:
    return poly(L[0])
  a=knapsack(L[:len(L)//2])
  b=knapsack(L[len(L)//2:])
  return pm(a,b)[:K+1]

for i in range(1,1<<H):
  X=[0]*W
  for j in range(H):
    if i&(1<<j):
      for k in range(W):
        if C[j][k]=='#':
          X[k]+=1
  DP=knapsack(X)[K]
  if len(DP)>K:
    P+=DP[K]
print(P)

Submission status: Runtime Error

Solution code:
from math import *
from cmath import rect

def dft(f,x):
  if len(f)==1:
    return
  f0,f1=f[0::2],f[1::2]
  dft(f0,x)
  dft(f1,x)
  z=rect(1,x*2*acos(-1)/len(f))
  n=1+0j
  for i in range(len(f)):
    f[i]=f0[i%len(f0)]+n*f1[i%len(f1)]
    n=n*z

def pm(p,q):
  siz=1
  while len(p)+len(q)>siz:
    siz*=2
  np=[]
  nq=[]
  for i in range(len(p)):
    np.append(rect(p[i],0))
  for i in range(len(q)):
    nq.append(rect(q[i],0))
  while len(np)<siz:
    np.append(0+0j)
  while len(nq)<siz:
    nq.append(0+0j)
  dft(np,1)
  dft(nq,1)
  for i in range(siz):
    np[i]=np[i]*nq[i]
  dft(np,-1)
  EPS=0.1
  for i in range(siz):
    np[i]=int(np[i].real/siz+EPS)
  return np

H,W,K=map(int,input().split())
C=[input() for i in range(H)]
DP=[0]*(K+1)
X=[]
P=0

def poly(x):
  r=[0]*x
  r.append(1)
  r[0]+=1
  return r

def knapsack(L):
  if len(L)==1:
    return poly(L[0])
  a=knapsack(L[:len(L)//2])
  b=knapsack(L[len(L)//2:])
  return pm(a,b)[:K+1]

for i in range(1,1<<H):
  X=[0]*W
  for j in range(H):
    if i&(1<<j):
      for k in range(W):
        if C[j][k]=='#':
          X[k]+=1
  P+=knapsack(X)[K]
print(P)

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
state = np.zeros((H, W), dtype=int)
for h in range(H):
  hlist = input()
  for w in range(W):
    if hlist[w] == "#":
      state[h][w]=1

startb = np.sum(state)
count = 0

if startb < K:
  print(0)
else:
  h_l = 2**H
  w_l = 2**W
  for h in range(h_l):
    for w in range(w_l):
      t1 = [int(i) for i in list(str(bin(h))[2:])]
      t2 = np.zeros(H-len(t1), dtype=int)
      wflag = np.append(t2, t1)
      state_t = state * np.array([wflag]*W).T

      t1 = [int(i) for i in list(str(bin(w))[2:])]
      t2 = np.zeros(W-len(t1), dtype=int)
      hflag = np.append(t2, t1)
      state_t = state_t * np.array([hflag]*H)

      if np.sum(state_t)==K:
        count=count+1
  print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
H,W,K = map(int,input().split())
ll = []
for h in range(H):
    l = []
    for s in input():
        if s == ".":
            l.append(0)
        else:
            l.append(1)
    ll.append(l)
cnt = 0
for bh in range(2 ** H):
    for bw in range(2 ** W):
        nn = np.asarray(ll)
        k = 0
        for h in range(H):
            if (bh & 2 ** h) >> h == 0:
                continue
            nn[h] = np.array([0] * W)
        for w in range(W):
            if (bw & 2 ** w) >> w == 0:
                continue
            nn[:,w] = np.array([0] * W)
        for h in range(H):
            for w in range(W):
                k += nn[h][w]
        if k == K:
            cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest

a = input().rstrip().split(" ")

H = int(a[0])  # 行
W = int(a[1])  # 列
K = int(a[2])  # 操作後に残る黒いマスの数

m = []
for i in range(H):
    n = list(input())
    m.append(n)

# print(m)
ans = 0

for maskR in range(1 << H):
    for maskC in range(1 << W):
        black = 0
        for i in range(H):
            for j in range(W):
                if (maskR >> i & 1) == 0 and (maskL >> j & 1) == 0 and m[i][j] == '#':
                    black += 1
        if black == k:
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest

a = input().rstrip().split(" ")

H = int(a[0])  # 行
W = int(a[1])  # 列
K = int(a[2])  # 操作後に残る黒いマスの数

m = []
for i in range(H):
    n = list(input())
    m.append(n)

# print(m)
ans = 0

for maskR in range(1 << H):
    for maskC in range(1 << W):
        black = 0
        for i in range(H):
            for j in range(W):
                if (maskR >> i & 1) == 0 and (maskL >> j & 1) == 0 and m[i][j] == '#':
                    black += 1
        if black == k:
            ans += 1
print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 3 2
..#
###"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3 4
..#
###"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """2 2 3
##
##"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """6 6 8
..##..
.#..#.
#....#
######
#....#
#....#"""
        output = """208"""
        self.assertIO(input, output)


if __name__ == "__main__":
    unittest.main()

Submission status: Runtime Error

Solution code:
h, w, k = map(int, input().split())
mark = [input() for _ in range(h)]
ans = 0

for bit_h in range(1 << h):
  i_list = []
  for i in range(h):
    if bit_h & 1:
      i_list.append(i)
    bit_h >>= 1
  for bit_w in range(1 << w):
    count = 0
    j_list = []
    for j in range(w):
      if bit_w & 1:
        j_list.append(bit_w & 1)
      bit_w >>= 1
    for i in i_list:
      for j in j_list:
        if mark[i][j] = '#':
          count += 1
    if count == k:
      ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
count=0
for H in range(h<<1):
  for W in range(W<<1):
    b=0
    for i in range(h):
      for j in range(w):
        if (H >> i) & 1 == 0 and (W >> j) & 1 == 0 and c[i][j] == "#":
          b+=1
    if b==k:
      count+=1
print(count)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
c=[input() for _ in range(h)]
count=0
for H in range(h<<1):
  for W in range(W<<1):
    b=0
    for i in range(h):
      for j in range(w):
        if (W >> i) & 1 == 0 and (H >> j) & 1 == 0 and c[i][j] == "#":
          b+=1
    if b==k:
      count+=1
print(count)

Submission status: Runtime Error

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

ans = 0
for i in 2**H:
    for j in 2**W:
        tmp = 0
        for ii in range(H):
            for jj in range(W):
                
                if C[ii][jj] == '#' and (i >> ii) == 0 and (j >> jj) == 0:
                    tmp += 1
        if tmp == K:
            ans += 1
            
print(ans)

Submission status: Runtime Error

Solution code:
H,W,K=map(int,(input().split()))
board=[list(input().split()) for _ in range(H)]
ans=0
for paint_H in range(2**H):
    for paint_W in range(2**W):
        cnt=0
        for i in range(H):
            for j in range(W):
                if(paint_H>>i)&1==0 and (paint_W>>j)&1==0:
                    if board[i][j]=="#":
                        cnt+=1
        if cnt==K:
            ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
lst=[]
for i in h:
  lst=list(map(str,input())
print(lst)

Submission status: Runtime Error

Solution code:
import numpy as np

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

C = np.frombuffer(read(), dtype='S1').reshape(H, -1)
print(C)

Submission status: Runtime Error

Solution code:
import copy
h,m,k=map(int,input().split())
cl=[list(map(str,input().split())) for _ in range(h)]
b=h+m
c1=0
for i in range(2**b):
    c=copy.deepcopy(cl)
    bit=format(i, 'b').zfill(b)
    for j in range(h):#行
        if bit[j]=='1':
            for u in range(m):
                c[j][u]='+'
    
    for l in range(h,b):#列
        if bit[l]=='1':
            for o in range(h):
                c[o][l-h]='+'
    
    c2=0
    for p in range(h):
        c2+=c[p].count('#')
    if c2==k:c1+=1

print(c1)

Submission status: Runtime Error

Solution code:
import copy
h,m,k=map(int,input().split())
cl=[list(map(input().split())) for _ in range(h)]
b=h+m
c1=0
for i in range(2**b):
    c=copy.deepcopy(cl)
    bit=format(i, 'b').zfill(b)
    for j in range(h):#行
        if bit[j]=='1':
            for u in range(m):
                c[j][u]='+'
    
    for l in range(h,b):#列
        if bit[l]=='1':
            for o in range(h):
                c[o][l-h]='+'
    
    c2=0
    for p in range(h):
        c2+=c[p].count('#')
    if c2==k:c1+=1

print(c1)

Submission status: Runtime Error

Solution code:
import copy
h,m,k=map(int,input().split())
cl=[list(input().split()) for _ in range(h)]
b=h+m
c1=0
for i in range(2**b):
    c=copy.deepcopy(cl)
    bit=format(i, 'b').zfill(b)
    for j in range(h):#行
        if bit[j]=='1':
            for u in range(m):
                c[j][u]='+'
    
    for l in range(h,b):#列
        if bit[l]=='1':
            for o in range(h):
                c[o][l-h]='+'
    
    c2=0
    for p in range(h):
        c2+=c[p].count('#')
    if c2==k:c1+=1

print(c1)