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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos

    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)

show_flg=False
show_flg=True

ans=0

h,w,K=LI()
m=[]
for i in range(h):
    m+=[[1 if i=='#' else 0 for i in input()]]
    
H=1<<h
W=1<<w
for i in range(H):
    for j in range(W):
        tmp=0
        for k in range(h):
            for l in range(w):
                if (i>>k)&1 or (j>>l)&1:
                    continue
                tmp+=m[k][l]
        if tmp==K:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
c = []
for _ in range(h):
  c.append(input())
  
cols = ['{:06b}'.format(i)[6-w:] for i in range(2**w)]
rows = ['{:06b}'.format(i)[6-h:] for i in range(2**h)]

ans = 0
for row in rows:
  for col in cols:
    cnt = 0
    for i in range(h):
      for j in range(w):
        if row[i] == '0' and col[j] == '0':
          if c[i][j] == '#':
            cnt += 1
          if cnt > k:
            break
      if cnt > k:
        break
    else:
      if cnt == k:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
h, w, k = map(int,input().split())
c = [list(input()) for _ in range(h)]

def cnt(i, j):
    res = 0
    for s in combinations(range(h),i):
        for t in combinations(range(w), j):
            count = 0
            for u in range(h):
                for v in range(w):
                    if u in s:continue
                    if v in t:continue
                    if c[u][v] == '#':
                        count += 1
            if count == k:res += 1
    return res    

ans = 0
for i in range(h + 1):
    for j in range(w + 1):
        ans += cnt(i, j)
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        c = C.copy()
        cnt = 0
        for a in range(H):
            for b in range(W):
                cell = c[a][b]
                if cell == '#':
                    cnt += 1
                if (i>>a & 1 or j>>b & 1) and cell == '#':
                    cnt -= 1
                    c[a][b] == '.'
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
from copy import deepcopy
def main(H, W, K, C):
    def count(matrix):
        return sum(1 for i in range(H) for j in range(W) if matrix[i][j] == '#')

    ans = 0
    for iii in range(1 << H):
        for jjj in range(1 << W):
            I, J = iii, jjj
            mt = deepcopy(C)
            for i in range(H):
                if I & 1:
                    for jj in range(W):
                        mt[i][jj] = 'R'
                I >>= 1
            for j in range(W):
                if J & 1:
                    for ii in range(H):
                        mt[ii][j] = 'R'
                J >>= 1
            if count(mt) == K:
                ans += 1
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    C = [list(input().rstrip()) for _ in range(H)]
    main(H, W, K, C)

Submission status: Accepted

Solution code:
from itertools import product 

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

c = [list(input()) for i in range(H)]

ans =0
for i in product([0,1],repeat=H):#1の行を赤く塗る
    for j in product([0,1],repeat=W):#1の列をry

        count = 0
        for n in range(0,H,1):
            for m in range(0,W,1):
                if i[n]==1 or j[m] == 1:
                    continue
                if c[n][m]=="#":
                    count+=1
        if count ==K:
            ans +=1

print(ans)

Submission status: Accepted

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

cnt_1 = 0
for n_h in range(1 << H):
    idx_h = set()
    cnt_h = 0
    while n_h > 0:
        if n_h & 1:
            idx_h.add(cnt_h)

        cnt_h += 1
        n_h >>= 1

    for n_w in range(1 << W):
        idx_w = set()
        cnt_w = 0
        while n_w > 0:
            if n_w & 1:
                idx_w.add(cnt_w)

            cnt_w += 1
            n_w >>= 1

        cnt_bkl = 0
        for h in range(H):
            if h in idx_h:
                continue

            for w in range(W):
                if w in idx_w:
                    continue

                if grid[h][w] == '#':
                    cnt_bkl += 1

        if cnt_bkl == K:
            cnt_1 += 1


print(cnt_1)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

h,w,k = m()

po = [list(input()[:-1]) for i in range(h)]

hei = 2 ** h

wid = 2 ** w

dph = [0 for i in range(h)]

dpw = [0 for i in range(w)]
ans = 0
for i in range(hei):
	ii = str(bin(i)[2:]).zfill(h)
	#print(ii)
	for j in range(h):
		if ii[j] == "1":
			dph[j] = 1
		else:
			dph[j] = 0

	
	for j in range(wid):
		jj = str(bin(j)[2:]).zfill(w)
		#print(jj)
		for ii in range(w):
			if jj[ii] == "1":
				dpw[ii] = 1
			else:
				dpw[ii] = 0

		co = 0
		for ii in range(h):
			for jj in range(w):
				if dph[ii] or dpw[jj]:
					continue
				elif po[ii][jj] == "#":
					co += 1
		if co == k:
			ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W, K = map(int, input().split())
    c = [None] * H
    for i in range(H):
        c[i] = input()

    ans = 0
    for i in range(2**H):
        for j in range(2**W):
            tmp = 0
            # print(i,j)
            for ii in range(H):
                for jj in range(W):
                    # print(ii,jj)
                    if c[ii][jj] == '#':
                        # print((i >> ii)&1,)
                        if ((i >> ii)&1) or ((j >> jj)&1):
                            pass
                        else:
                            tmp += 1
            # print(tmp)
            if tmp == 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 _ in range(H)]
ans = 0
for i in range(2 ** H):
    h = []
    for j in range(H): 
        if ((i >> j) & 1):
            h.append(j)
    for k in range(2 ** W):
        w = []
        for l in range(W):
            if ((k >> l) & 1):
                w.append(l)
        cnt = 0
        for a in range(H):
            for b in range(W):
                if a not in h and b not in w and C[a][b] == "#":
                    cnt += 1
        if cnt == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def isValid(tmp_r, tmp_c):
    ret = 0
    for row in range(H):
        for col in range(W):
            ret += 1 if c[row][col] == '#' and not row in tmp_r and not col in tmp_c else 0
    return ret == K

def solve():
    ret = 0
    for ri in range(pow(2, H)):
        tmp_r = []
        for rj in range(H):
            if ri >> rj & 1:
                tmp_r.append(rj)
        for ci in range(pow(2, W)):
            tmp_c = []
            for cj in range(W):
                if ci >> cj & 1:
                    tmp_c.append(cj)

            ret += 1 if isValid(tmp_r, tmp_c) else 0
    print(ret)

if __name__ == "__main__":
    H, W, K = map(int, input().split())
    c = []
    for _ in range(H):
        c.append(list(input()))
    solve()

Submission status: Accepted

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


def solve(H, W, K, C):
    from itertools import compress, product
    def f(hs, ws):
        k = 0
        for h in range(H):
            if h in hs:
                continue
            for w in range(W):
                if w in ws:
                    continue
                if C[h][w] == "#":
                    k += 1
        return k == K
    ans = 0
    for hs in (set(compress(range(H), p)) for p in product([True, False], repeat=H)):
        for ws in (set(compress(range(W), p)) for p in product([True, False], repeat=W)):
            if f(hs, ws):
                ans += 1
    return ans

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W, K = map(int, input().split())
    C = [input() for _ in range(H)]
    print(solve(H, W, K, C))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int,input().split())
c = [list((ord(x) - 46) // (-11) for x in list(input())) for i in range(H)]   
ans = 0
for i in itertools.product((0,1), repeat=W):    
    for j in itertools.product((0,1), repeat=H):
        temp = 0
        for a in range(W):
            for b in range(H):
                if i[a] == 1 and j[b] == 1:
                    temp += c[b][a]
        if temp == K:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    black = [[c == '#' for c in C] for C in args[1:]]

    ret = 0
    for x in range(2**w):
        for y in range(2**h):
            cnt = 0
            for i in range(w):
                for j in range(h):
                    if (x >> i) & 1 and (y >> j) & 1 and black[j][i]:
                        cnt += 1
            if cnt == k:
                ret += 1
    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
H,W,K = map(int,input().rstrip().split(" "))
s= []
ans = 0
for i in range(H):
    s.append(list(input()))

for i in range(2 ** H):
    l = [0 for i in range(W)]
    for i2 in range(H):
        if (i >> i2) & 1:
            for i3 in range(W):
                if s[i2][i3] == "#":
                    l[i3] += 1
    for i2 in range(2 ** W):
        q = 0
        for i3 in range(W):
            if (i2 >> i3) & 1:
                q += l[i3]
        if q == K:
            ans += 1
print(ans)

Submission status: Accepted

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

res = 0
for a in range(2 ** h):
    for b in range(2 ** w):
        l_1 = []
        l_2 = []
        for i in range(h):
            if a >> i & 1:
                l_1.append(i)
        for i in range(w):
            if b >> i & 1:
                l_2.append(i)
        cnt = 0
        for c in range(h):
            for d in range(w):
                if c in l_1 or d in l_2:
                    continue
                if C[c][d] == '#':
                    cnt += 1
        if cnt == k:
            res += 1

print(res)

Submission status: Accepted

Solution code:
H,W,K,*c = open(0).read().split()
H = int(H)
W = int(W)
K = int(K)
ans = 0

selectedh = [False for i in range(H)]
selectedw = [False for i in range(W)]
for i in range(2 ** (H)):
    for j in range(H):
        if i >> j & 1:
            selectedh[j] = True
        else:
            selectedh[j] = False
    for i in range(2 ** (W)):
        for j in range(W):
            if i >> j & 1:
                selectedw[j] = True
            else:
                selectedw[j] = False
        temp = 0
        for k in range(H):
            if selectedh[k] == True:
                continue
            else:
                for l in range(W):
                    if selectedw[l] == True:
                        continue
                    else:
                        if c[k][l] == '#':
                            temp += 1
        if temp == K:
            ans += 1
print(ans)

Submission status: Accepted

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

def get_bitset(n): #get n-length-bitset
    pattern = []
    for i in range(2**n):
        tmp = []
        for j in range(n):
            if i >> j & 1:
                tmp.append(1)
            else:
                tmp.append(0)
        pattern.append(tmp)
    return pattern

row = get_bitset(h)
col = get_bitset(w)
ans = 0
for i_l in row:
    for j_l in col:
        count = 0
        for i in range(h):
            for j in range(w):
                if i_l[i] == 0 and j_l[j] == 0:
                    if table[i][j] == "#":
                        count += 1
        if count == k:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

H, W, K = getNM()
maze = [list(input()) for i in range(H)]
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            maze[i][j] = 0
        else:
            maze[i][j] = 1

# 縦
cnt = 0
for bit_h in range(1 << H):
    # 横
    for bit_w in range(1 << W):
        opt = 0
        alta = copy.deepcopy(maze)
        for i in range(H):
            for j in range(W):
                if bit_h & (1 << i):
                    alta[i][j] = 0
                if bit_w & (1 << j):
                    alta[i][j] = 0
        for i in range(H):
            opt += sum(alta[i])
        if opt == K:
            cnt += 1
print(cnt)

Submission status: Accepted

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

ans = 0

from itertools import product
for b_h in product((True, False), repeat=H):
  for b_w in product((True, False), repeat=W):
    count = 0
    for i in range(H):
      for j in range(W):
        if b_h[i] and b_w[j] and C[i][j] == '#':
          count += 1
    if count == K:
      ans += 1

print(ans)

Submission status: Accepted

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

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


def check(C, row, col):
    cnt = 0
    for i in range(H):
        for j in range(W):
            if row[i] == 0 and col[j] == 0 and C[i][j] == '#':
                cnt += 1

    return cnt
            
ans = 0
for i in range(1<<H):
    row = [0]*H
    for j in range(H):
        if 1&(i>>j):  # 右シフトして論理積（bit全探索）
            row[j] = 1

    for i in range(1<<W):
        col = [0]*W
        for j in range(W):
            if 1&(i>>j):  # 右シフトして論理積（bit全探索）
                col[j] = 1

        # print(row, col)
        if check(C, row, col) == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
H,W,K = map(int,input().split())
col = [[0]*W for _ in range(H)]
for i in range(H):
    s = list(input())[:-1]
    for j in range(W):
        if s[j] == "#":
            col[i][j] = 1
yoko = [0]*H
tate = [0]*W
for i in range(H):
    for j in range(W):
        yoko[i] += col[i][j]
for i in range(W):
    for j in range(H):
        tate[i] += col[j][i]
ALL = 0
for i in range(H):
    for j in range(W):
        ALL += col[i][j]
ans = 0
for i in range(2**H):
    bitlisth = deque()
    for j in range(H):
        if ((i >> j) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
            bitlisth.appendleft(1)
        else:
          	bitlisth.appendleft(0)
    bitlisth = list(bitlisth)
    for k in range(2**W):
        bitlistw = deque()
        for l in range(W):
            if ((k >> l) & 1): #2進数表示のj桁目(0桁目から数える)が1かどうか
                bitlistw.appendleft(1)
            else:
                bitlistw.appendleft(0)
        bitlistw = list(bitlistw)
        a = ALL
        h = []
        w = []
        for p in range(H):
            if bitlisth[p] == 1:
                a -= yoko[p]
                h.append(p)
        for q in range(W):
            if bitlistw[q] == 1:
                a -= tate[q]
                w.append(q)
        for pp in h:
            for qq in w:
                a += col[pp][qq]
        if a == K:
            ans += 1
print(ans)

Submission status: Accepted

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

WHITE = 0
BLACK = 1
RED = 2

board = [[WHITE] * W for i in range(H)]

for i in range(H):
    s = input()
    for j, v in enumerate(s):
        if v == '#':
            board[i][j] = BLACK


ans = 0
for rowmask in itertools.product([0, 1], repeat=H):
    for colmask in itertools.product([0, 1], repeat=W):
        cur = copy.deepcopy(board)
        blackCount = 0
        for i, r in enumerate(cur):
            for j, w in enumerate(r):
                if rowmask[i] == 1 or colmask[j] == 1:
                    continue
                if w == WHITE:
                    continue
                blackCount += 1
        if blackCount == K:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K = [int(_n) for _n in input().split()]
WHITE = 0
BLACK = 1
grid = []
for i in range(H):
    s = input()
    grid.append([])
    for c in s:
        grid[i].append(BLACK if c == "#" else WHITE)
res = 0
for tate in range(2**H):
    for yoko in range(2**W):
        # print("-----")
        grid2 = copy.deepcopy(grid)
        for t in range(H):
            if ((tate >> t) & 1) == 1:
                # print(t)
                grid2[t] = [WHITE]*W
        # print("-")
        for y in range(W):
            if ((yoko>>y) & 1) == 1:
                # print(y)
                for h in range(H):
                    grid2[h][y] = WHITE
        r = 0
        for i in range(H):
            for j in range(W):
                if(grid2[i][j] == BLACK):
                    r += 1
        # print(grid2)
        # print(r)
        if r == K:
            res += 1
            # print(tate,yoko)

print(res)