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:
# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000)

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)

def ncr(n, r,  fact, ifact,MOD=mod):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    #rdivisors=[]
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
    return divs_number


def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True

def print_arr2d(a):
    for i in a:
        prr(i)
    
def ceil(n, k=1): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []
def write(s): return sys.stdout.write(s)












###################################################################
# code goes here
from itertools import combinations,product
def main():
    h,w,k=mi()
    matrix=[[0 for i in range(w)] for j in range(h)]
    total=0
    ones=[]
    for i in range(h):
        c=input()
        for j in range(w):
            if c[j]==".":
                matrix[i][j]=0
            else:
                matrix[i][j]=1
                ones.append([i,j])
                total+=1
    answer=0

    for i in range(h+1):
        for rowl in combinations(list(range(h)),i):
            for j in range(w+1):
                for coll in combinations(list(range(w)),j):
                    count=0
                    for element in ones:
                        if element[0] in rowl or element[1] in coll:
                            count+=1
                    if count==total-k:
                        answer+=1
    print(answer)


                

                    




        
    
        
        
    


            


            
                
            

            



                






        
        


    
    
                

    

""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda: self.buffer.read().decode('ascii')
            self.readline = lambda: self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

""" main function"""

if __name__ == '__main__':
    main()
    #threading.Thread(target=main).start()

Submission status: Accepted

Solution code:
import numpy as np
import copy

H, W, K = map(int, input().split())
if H == 1:
    d = list(map(str, input().split()))
    X = list(d[0])
    black = 0
    for i in range(W):
        if X[i] == "#":
            black += 1

    t = 0
    s = "0" + str(W) + "b"

    #消すバージョン
    if K == 0:
        t += 2**W

    #消さない
    for i in range(2**W):
        black_xx = black
        WW = format(i, s)
        for j in range(W):
            if WW[j] == "1" and X[j] == "#":
                black_xx -= 1
        if black_xx == K:
            t += 1

    print(t)

elif W == 1:
    X = []
    for i in range(H):
        X.append(input())
    black = 0
    for i in range(H):
        if X[i] == "#":
            black += 1

    t = 0
    s = "0" + str(H) + "b"

    #消すバージョン
    if K == 0:
        t += 2**H

    #消さない
    for i in range(2**H):
        black_xx = black
        HH = format(i, s)
        for j in range(H):
            if HH[j] == "1" and X[j] == "#":
                black_xx -= 1
        if black_xx == K:
            t += 1

    print(t)



else:
    d = list(map(str, input().split()))
    X = list(d[0])
    for i in range(H - 1):
        d = list(map(str, input().split()))
        d = list(d[0])
        X = np.vstack((X, d))

    black = 0
    for i in range(X.shape[0]):
        for j in range(X.shape[1]):
            if X[i,j] == "#":
                black += 1

    t = 0
    s1 = "0" + str(H) + "b"
    s2 = "0" + str(W) + "b"
    for i in range(2**H):
        for j in range(2**W):

            XX = copy.copy(X)
            black_xx = black
            HH = format(i, s1)
            WW = format(j, s2)

            for ii in range(H):
                if HH[ii] == "1":
                    for iii in range(W):
                        if XX[ii,iii] == "#":
                            black_xx -= 1
                            XX[ii,iii] = "."
            for jj in range(W):
                if WW[jj] == "1":
                    for jjj in range(H):
                        if XX[jjj,jj] == "#":
                            black_xx -= 1
                            XX[jjj,jj] = "."
            if black_xx == K:
                t += 1

    print(t)

Submission status: Accepted

Solution code:
import itertools
import copy

H, W, k = map(int, input().split())
matrix = []

for h in range(H):
    matrix.append(list(input()))

def count_black(mat):
    flat = list(itertools.chain.from_iterable(mat))
    b_sum = flat.count('#')
    return b_sum

ans = 0
for h in range(2 ** H):
    for w in range(2 ** W):
        tmp_matrix = copy.deepcopy(matrix)
        for i in range(H):
            if (h >> i) & 1:
                tmp_matrix[i][:] = ['.'] * W
        for j in range(W):
            if (w >> j) & 1:
                for i in range(H):
                    tmp_matrix[i][j] = '.'
        c = count_black(tmp_matrix)
        if c == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
h, w, k = list(map(int, input().split()))
C = list(list(input()) for _ in range(h))
c = np.array(C)
l1, l2 = [()], [()]
H = [i for i in range(h-1, -1, -1)]
W = [i for i in range(w-1, -1, -1)]
cnt = 0

for i in range(h-1):
    l1+=list(itertools.combinations(H, i+1))
for i in range(w-1):
    l2+=list(itertools.combinations(W, i+1))

for i in l1:
    for j in l2:
        c2 = c
        for a in i:
            c2 = np.delete(c2, a, 0)
        for b in j:
            c2 = np.delete(c2, b, 1)
        if np.count_nonzero(c2 == '#') == k:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

cc=0
h, w, k= map(int, input().split())
ans=np.zeros((h, w), dtype=int)
for ih in range(0,h):
  a = input()
  for iw in range (0,w):
    if (a[iw] == '.'): ans[ih,iw]=2
    if (a[iw] == '#'): ans[ih,iw]=1
      
hlist=list(itertools.product('01',repeat=h))
wlist=list(itertools.product('01',repeat=w))

for ih in hlist:
  for iw in wlist:
    ans1=ans.copy()
#    print (int(ih[0]))
#    print (int(iw[3]))
#    print (ans)
#    print (ans1)
    for iiih in range(0,h): 
      if (ih[iiih] == '0'): ans1[iiih,:]=0
    for iiiw in range(0,w):
      if (iw[iiiw] == '0'): ans1[:,iiiw]=0
#    print (ans1)
    
    kkk=np.count_nonzero(ans1 == 1)
    if (k == kkk): cc+=1
    
print (cc)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import copy

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

row = []
for _ in range(H):
    C, = map(str, input().split())
    row.append(list(C))

ans = 0
for i in range(2**H):
    tmp = copy.deepcopy(row)

    i_list = list(map(int, list(format(i, 'b'))))
    for ii, il in enumerate(i_list[::-1]):
        if il==1:
            for w in range(W):
                tmp[-1-ii][w] = 'r'

    for j in range(2**W):
        tmp2 = copy.deepcopy(tmp)
        j_list = list(map(int, list(format(j, 'b'))))
        for jj, jl in enumerate(j_list[::-1]):
            if jl==1:
                for h in range(H):
                    tmp2[h][-1-jj] = 'r'


        count = sum([t.count('#') for t in tmp2])
        if count==K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

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


def count_s(s):
    cnt = 0
    for ss in s:
        cnt += ss.count('.')
    return h*w-cnt

out=0
xx=h+w
if count_s(data) == k:
    out = 1

for kk in range(1,xx+1):
    lst = list(itertools.combinations([x for x in range(xx)], kk))
    for ll in lst:
        dd = copy.deepcopy(data)
        for l in ll:
            if l >= h:
                for i in range(h):
                    buf = dd[i]
                    dd[i]=buf[:l-h]+'.'+buf[l-h+1:]
            else:
                dd[l]='.'*w
        if count_s(dd) == k:
            out += 1

print(out)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
X = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
ans = 0
for ii in range(1 << H):
    for jj in range(1 << W):
        if sum([sum([X[i][j] for j in range(W) if jj >> j & 1]) for i in range(H) if ii >> i & 1]) == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = map(int, input().split())
_map = np.zeros((h, w), dtype = int)
ans = 0

def Count(k, s):
  _array = np.copy(_map)
  for j in range(s):
    if ((k >> j) & 1):
      if j < h:
        _array[j, :] = 0
      else:
        _array[:, j - h] = 0
        
  return np.sum(_array) == k

for i in range(h):
  _str = list(input())
  for j in range(w):
    if (_str[j] == "#"):
      _map[i, j] = 1
      
for i in range(2**(h + w)):
  _array = np.copy(_map)
  for j in range(h + w):
    if ((i >> j) & 1):
      if j < h:
        _array[j, :] = 0
      else:
        _array[:, j - h] = 0
        
  if np.sum(_array) == k:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import copy
from itertools import product
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]
C = np.array(C)

cnt = 0
for i in product([True, False], repeat=h):
    c = copy.deepcopy(C)
    c = np.array(c)
    for p, q in enumerate(i):
        if q:
            c[p, :] = "$"
    for j in product([True, False], repeat=w):
        d = copy.deepcopy(c)
        d = np.array(d)
        for s,t in enumerate(j):
            if t:
                d[:, s] = "$"
        if np.count_nonzero(d == "#") == k:
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

def count(arr,k,H,W):
    
    num_ans = 0

    for col in kumiawase(arr):
        countlist = [0]*W

        #print("col:")
        #printarr(col)
        #print()

        for i in range(len(col)):
            count = 0
            for j in range(len(col[0])):
                if col[i][j] == 1:
                    countlist[j]=countlist[j]+1
            #countlist.append(count)


        #print("countlist")
        #print(countlist)
        #print()
        for x in kumiawase(countlist):
            if sum(x) == k :
                num_ans += 1
        
    print(num_ans)

def kumiawase(list):
    #listから取り出すすべての組み合わせ：

    returnlist = []
    num_kumi = 2**len(list)
    for i in range(num_kumi):
        tmplist = []
        for j in range(len(list)):
            if (i >> j)%2 == 1:
                tmplist.append(list[j])

        returnlist.append(tmplist)
    
    return returnlist


def printarr(arr):
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            print(arr[i][j],end=" ")
        print()

if __name__ == "__main__":
    H,W,K = map(int,input().split())

    arr = []
    count_H = []
    total = 0
    for i in range(H):
        list = []
        inp = input()
        for j in range(W):
            num = 0
            if "." == inp[j]:
                list.append(0)
            else:
                list.append(1)
                num += 1
                total += 1
        arr.append(list)
        count_H.append(num)
    
    count_W = []
    for i in range(W):
        num = 0
        for j in range(H):
            num += 1
        count_W.append(num)

#    printarr(arr)


    count(arr,K,H,W)

Submission status: Accepted

Solution code:
import copy
# @patch('builtins.input', test.test_input)
def main():
    h, w, K = map(int, input().split())
    c = [list(input()) for _ in range(h)]
    ans = 0
 
    def get_list(n):
        s = list(range(n))
        n = len(s)
        l = []
        for i in range(2 ** n):
            bit_set = []
            for j in range(n):
                if ((i >> j) & 1):
                    bit_set.append(s[j])
            l.append(bit_set)
        return l
     
    ws = get_list(w)
    hs = get_list(h)
    for wws in ws:
        d = copy.deepcopy(c)
#         print(wws)
        for i in wws:
            for x in range(h):
                d[x][i] = '.'
        e = copy.deepcopy(d)
        for hhs in hs:
            f = copy.deepcopy(e)
            for j in hhs:
                for x in range(w):
                    f[j][x] = '.'
            # print(f)
            tmp = 0
            for x in range(h):
                tmp += f[x].count('#')
            if tmp == 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 i in range(h)]
ans = 0
for i in range(h+1):
  for j in range(w+1):
    for high in itertools.combinations(range(h),i):
      for width in itertools.combinations(range(w),j):
        C2 = copy.deepcopy(C)
        for hi in high:
          for l in range(w):
            C2[hi][l] = "."
        for wi in width:
          for m in range(h):
            C2[m][wi] = "."
        C2 = list(itertools.chain.from_iterable(C2))
        if C2.count("#") == k:
          ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from copy import copy

def red(l, r, prefix):
    for index, i in enumerate(r):
        i = int(i)
        if i:
            if prefix == 0:
                l[index] = 'r'
            else:
                l[:, index] = 'r'

    return l

def main():
    h, w, k = map(int, input().split())
    cnt = 0
    list_ = []
    box = []
    for _ in range(h):
        l = list(input())
        list_.append(l)
    list_ = np.array(list_)
    x = copy(list_)
    for i in range(2**h):
        x1 = copy(x)

        r = format(i, f'0{h}b')
        x1 = red(x1, r, 0)
        for j in range(2**w):
            x2 = copy(x1)
            r = format(j, f'0{w}b')
            x2 = red(x2, r, 1)
            if np.count_nonzero(x2 == '#') == k:
                cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
C = [["" for _ in range(w)] for _ in range(h)]
c = 0
for j in range(h):
    s = input()
    for i in range(w):
        C[j][i] = s[i]
        if s[i] == "#":
            c += 1

ans = 0
for bit_i in range(1<<h):
    for bit_j in range(1<<w):
        btor = 0
        for i in range(h):
            if bit_i & (1<<i):
                for ij in range(w):
                    if C[i][ij] == "#":
                        btor += 1
        for j in range(w):
            if bit_j & (1<<j):
                for ji in range(h):
                    if C[ji][j] == "#":
                        btor += 1
        for i in range(h):
            for j in range(w):
                if (bit_j & (1<<j)) and (bit_i & (1<<i)):
                    if C[i][j] == "#":
                        btor -= 1
        if c - btor == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import numpy as np
    import sys

    readline = sys.stdin.readline    # 1行だけ文字列にする

    H, W, K = map(int, readline().split())
    c = [list(readline().strip()) for _ in [0] * H]

    # matrixは文字列#とそれ以外でなる時，#を1に，それ以外を0にする
    c = np.array([[1 if c[i][j] == "#" else 0
                 for j in range(W)]
                 for i in range(H)], dtype=np.int64)

    ans = 0
    
    for bit_i in range(1 << H):
        lst_y = []
        for i in range(H):
            if bit_i & (1 << i):
                lst_y.append(i)
        for bit_j in range(1 << W):
            lst_x = []
            for j in range(W):
                if bit_j & (1 << j):
                    lst_x.append(j)
            fig = c[:]
            fig = np.delete(fig, lst_y, axis=0)
            fig = np.delete(fig, lst_x, axis=1)
            if np.count_nonzero(fig == 1) == K:
                ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import io,sys,copy
sys.setrecursionlimit(10**6)


def main():
    h,w,poi = map(int,input().split())
    G = []
    for _ in range(h):
        s = input()
        temp = []
        for i in s:
            temp.append(i)
        G.append(temp)
    
    ans = 0
    for i in range(0b1<<w):
        for j in range(0b1<<h):
            G_sub = copy.deepcopy(G)
            s = i
            k = 0
            while s > 0:
                r = s%2
                s = s//2
                if r == 1:
                    for y in range(h):
                        G_sub[y][k] = "%"
                k+=1
            
            s = j
            k = 0
            while s > 0:
                r = s%2
                s = s//2
                if r == 1:
                    for x in range(w):
                        G_sub[k][x] = "%"
                k+=1
            
            ct = 0
            for g in G_sub:
                ct+=g.count("#")
            if ct == poi:
                ans+=1
    
    print(ans)
main()

Submission status: Accepted

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


def check(use_rows, use_cols):
    count = 0
    for i in range(H):
        if i in use_rows:
            continue
        for j in range(W):
            if j in use_cols:
                continue
            if C[i][j] == '#':
                count += 1
    return count


count = 0
for bit_row in range(2 ** H):
    use_rows = set()
    for i in range(H):
        if (bit_row >> i & 1):
            use_rows.add(i)

    for bit_col in range(2 ** W):
        use_cols = set()
        for j in range(W):
            if (bit_col >> j & 1):
                use_cols.add(j)

        # print(bit_row, bit_col, use_rows, use_cols)
        if K == check(use_rows, use_cols):
            # print(use_rows, use_cols)
            count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import copy


def bw(cell):
    if(cell=='.'):
        return(0)
    else:
        return(1)

def getBin(number, total):
    return bin(number)[2:].zfill(total)

para_line = list(map(int,input().split(' ')))
board = np.zeros((para_line[0],para_line[1]))
for n in range(para_line[0]):
    board[n] = np.array(list(map(bw,list(input()))))

fil_h_num = [list(map(int, getBin(i, para_line[0]))) for i in range(2**para_line[0])]

fil_h = []

for i in fil_h_num:
    fil_h.append(list(map(bool,i)))

fil_w_num = [list(map(int, getBin(i, para_line[1]))) for i in range(2**para_line[1])]

fil_w = []

for i in fil_w_num:
    fil_w.append(list(map(bool,i)))

cnt = 0

for f in fil_h:
    now_board = copy.deepcopy(board[f])
    for w in fil_w:
        if(int(np.sum(now_board[:,w]))==para_line[2]):
            cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools as ito
import copy
[H, W, K]=list(map(int, input().split()))
xlist=[]
for i in range(H):
    xlist.append(input().split())
clist=[]
for x in xlist:
    y=[]
    for l in x[0]:
        y.append(l)
        #print(l)
    clist.append(y)
#print(clist)
gyochange=[]
retuchange=[]
for j in range(W+1):#列数
    ls2=ito.combinations(range(W),j)
    for retu in ls2:
        retuchange.append(retu)
for i in range(H+1):#行数
    ls1=ito.combinations([k for k in range(H)],i)
    for gyo in ls1:
        gyochange.append(gyo)
#print(gyochange)
#print(retuchange)
ans=0
cc=copy.deepcopy(clist)
for gch in gyochange:
    for rch in retuchange:
        clist=copy.deepcopy(cc)
        #print(gch,rch)
        for g in gch:
            for j in range(W):
                clist[g][j]='r'
        for r in rch:
            for i in range(H):
                clist[i][r]='r'
        clist=list(ito.chain.from_iterable(clist))
        #print(clist,clist.count('#'))
        if clist.count('#')==K:
            ans+=1
            #print('good')
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    H, W, K = MI()
    c = []
    for _ in range(H):
        x = []
        for s in ST():
            x.append(s)
        c.append(x)
    ans = 0
    for i in range(2 ** (H + W)):
        cc = deepcopy(c)
        x = 0
        z = 2 ** (H + W)
        while z:
            z = z >> 1
            if z & i:
                if x < H:
                    for k in range(W):
                        cc[x][k] = "."
                else:
                    xx = x - H
                    for k in range(H):
                        cc[k][xx] = "."
            x += 1
        total = 0
        for x in range(H):
            for y in range(W):
                if cc[x][y] == "#":
                    total += 1
        if total == K:
            ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import math
from decimal import Decimal, ROUND_DOWN
from collections import deque
from itertools import combinations
import copy

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (h, w, k) = [int(e) for e in lines[0].split(' ')]
    cs = []
    for i in range(1, h+1):
        l = [ c for c in lines[i]]
        cs.append(l)


    return (h, w, k, cs)


def solve(h, w, k, cs):


    def count_black(cs):
        return sum([len([ e for e in c if e == '#']) for c in cs])

    def gen_index(n):
        result = []
        for i in range(n+1):
            combs = combinations(range(n), i)
            for cb in combs:
                result.append(cb)
        return result

    cnt = 0
    for r in gen_index(h):
        for c in gen_index(w):
            ds = copy.deepcopy(cs)
            if debug:
                log("ds=%s" % ds)

            for i in range(h):
                for j in range(w):
                    if i in r or j in c:
                        ds[i][j] = 'R'

            
            cnt_black = count_black(ds)
            if cnt_black == k:
                if debug:
                    log("r=%s" % (r,))
                    log("c=%s" % (c,))
                    log("ds=%s" % ds)
                    log("cnt_black=%d" % cnt_black)
                cnt = cnt + 1


    return cnt
    


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()