Problem:


Score : 100 points

Problem Statement

There are N men and N women, both numbered 1, 2, \ldots, N.

For each i, j (1 \leq i, j \leq N), the compatibility of Man i and Woman j is given as an integer a_{i, j}.
If a_{i, j} = 1, Man i and Woman j are compatible; if a_{i, j} = 0, they are not.

Taro is trying to make N pairs, each consisting of a man and a woman who are compatible.
Here, each man and each woman must belong to exactly one pair.

Find the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Constraints

All values in input are integers.

1 \leq N \leq 21

a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

N
a_{1, 1} \ldots a_{1, N}
:
a_{N, 1} \ldots a_{N, N}

Output

Print the number of ways in which Taro can make N pairs, modulo 10^9 + 7.

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

There are three ways to make pairs, as follows ((i, j) denotes a pair of Man i and Woman j):

(1, 2), (2, 1), (3, 3)

(1, 2), (2, 3), (3, 1)

(1, 3), (2, 1), (3, 2)

Sample Input 2

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Sample Output 2

1

There is one way to make pairs, as follows:

(1, 2), (2, 4), (3, 1), (4, 3)

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

Sample Output 4

102515160

Be sure to print the number modulo 10^9 + 7.



Sample input:
3
0 1 1
1 0 1
1 1 1


Sample output:
3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=[]
dp=[-1]*(1<<n)
dp[(1<<n)-1]=1
mod=10**9+7
for i in range(n):
  a.append(list(map(int,input().split())))

def dfs(s, cnt):
    if dp[s] != -1:
        return dp[s]
    res = 0
    for i in range(n):
        if (s >> i) & 1 == 0 and a[cnt][i] == 1:
            res += dfs(s + (1 << i), cnt+1)
    dp[s] = res % mod
    return dp[s]
  
print(dfs(0,0))

Submission status: Accepted

Solution code:

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

from collections import Counter

M = 10**9 + 7
cur = [0] * (1<<N)
cur[0] = 1
for B in A:
    nxt = [0] * (1 << N)
    C = [1 << i for i, v in enumerate(B) if v == 1]
    for s, v in enumerate(cur):
        if v == 0:
            continue
        v %= M
        for b in C:
            if (s & b) != 0:
                continue
            nxt[s | b] += v
    cur = nxt
print(cur[(1<<N) - 1] % M)

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

mod = 10**9 + 7
dp = [-1] * (1 << n)
dp[0] = 1


def solve(bits, i):
    if dp[bits] != -1:
        return dp[bits]

    total = 0
    for j in range(n):
        if bits & (1 << j) and a[i][j]:
            total += solve(bits ^ (1 << j), i-1)

    dp[bits] = total % mod
    return dp[bits]


print(solve((1 << n) - 1, n-1))

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
for bit in range(1, 1 << N):
    i = 0
    for j in range(N):
        if bit >> j & 1 == 1:
            i += 1
    i -= 1
    for j in range(N):
        if a[i][j] == 1 and bit >> j & 1 == 1:
            dp[bit] += dp[bit & ~(1 << j)]
            dp[bit] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[-1] = 1
for i in range(N):
    bit = (1 << (N-i)) - 1
    while bit < (1 << N):
        for j in range(N):
            if a[i][j] == 1 and (bit >> j) & 1 == 1:
                dp[bit & ~(1 << j)] += dp[bit]
                dp[bit & ~(1 << j)] %= mod
        x = bit & -bit
        y = bit + x
        bit = (((bit & ~y) // x) >> 1) | y
print(dp[0])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                if dp[new_s] >= MOD: dp[new_s] -= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_o
O - Matching / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 人の男性たちと N 人の女性たちがいます。 
男性たちには 1,2,…,N と番号が振られています。 
同様に、女性たちには 1,2,…,N と番号が振られています。

各 i,j (1≤i,j≤N) について、男性 i と女性 j の相性の良し悪しが
    整数 ai,j によって与えられます。 
ai,j=1 ならば男性 i と女性 j は相性が良く、
    ai,j=0 ならば相性が悪いです。

太郎君は、相性が良い男女どうしのペアを N 組作ろうとしています。 
このとき、各男性および各女性は
    ちょうど 1 つのペアに属さなければなりません。

N 組のペアを作る方法は何通りでしょうか？ 
109+7 で割った余りを求めてください。

制約
入力はすべて整数である。
1≤N≤21
ai,j は0 または 1 である。

解法
配るDP
こういう時は事前にいくつの値が何個bit立ってるかを計算しておくのが良い

知見
    ================================================
    |bit_length = [0]                              |
    |for i in range(n):                            |
    |    bit_length += [x + 1 for x in bit_length] |
    |で2**n-1までのbitの立っている数を前計算できる     |
    ================================================
"""

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]

    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

dp=[0]*2**N
que=[0]

data=[[] for i in range(N+1)]
for i in range(2**N):
    cnt=0
    for j in range(N):
        if i&(1<<j)==0:
            continue
        cnt+=1
    data[cnt].append(i)
    
for j in range(N):
    if A[0][j]==1:
        num=1<<j
        dp[num]+=1
                
for i in range(N):
    for j in range(N):
        if A[i][j]==1:
            num=1<<j
            for u in data[i]:
                dp[u^num]=(dp[u^num]+dp[u])%mod

print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
dp = [[0]*(1<<n) for i in range(n+1)]
dp[0][0] = 1
for i in range(n):
  for bit in range(1<<n):
    if not dp[i][bit]: continue
    for k in range(n):
      if not (bit & 1<<k)  and A[i][k]:
        dp[i+1][bit|1<<k] += dp[i][bit]
        dp[i+1][bit|1<<k] %= mod
print(dp[n][(1<<n)-1])

Submission status: Accepted

Solution code:
mod = 10**9+7

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

DP = [0]*(1<<n)
DP[0] = 1

pow2 = [1<<i for i in range(n)]
cnt = [0]*(1<<n)
for i in range(1<<(n-1)):
    cnt[2*i] = cnt[i]
    cnt[2*i+1] = cnt[i]+1

for state in range(1, 1<<n):
    k = cnt[state]
    for j in range(n):
        if a[k-1][j] and (state>>j)&1:
            DP[state] += DP[state^pow2[j]]
    DP[state] %= mod
print(DP[-1])

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10**9 + 7

dp = [-1]*(2**N)
dp[0] = 1

# stateを二進数で表したときに、1である桁番号の女性がマッチングに参加
# 男性側は前から固定で女性と同じ人数だけ参加
def solve(state, c):
  global dp
  if dp[state] >= 0:
    return dp[state]
  else:
    dp[state] = 0 # 一旦、値を0に戻しておく
    for i in range(N):
      if state & (1<<i) and A[c-1][i]: 
        # i番目の女性がマッチングに参加しており、なおかつ
        # 最後の男性との相性が良い場合は、その2人でペアを作った場合の組合せを足し合わせる
        dp[state] += solve(state ^ (1<<i), c-1)
        dp[state] %= MOD
    
    return dp[state]

print(solve(2**N-1, N))

Submission status: Accepted

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))
#    print(dp)
    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1
#    print(dp)
    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod
#    print(dp)
    ans = dp[N][K]%mod
    print(ans)
    return

def examO():
    N = I()
    A = [LI() for _ in range(N)]
    loop = 2**N
    dp = [[0]*loop for _ in range(N+1)]
    dp[0][0] = 1
    for mask in range(loop):
        cur = 0
        for j in range(N):
            if mask&(1<<j)==(1<<j):
                cur +=1
        for i in range(N):
            if mask&(1<<i)==0 and A[i][cur]==1:
                dp[cur+1][mask|(1<<i)] += dp[cur][mask]
                dp[cur + 1][mask | (1 << i)] %=mod
#    print(dp)
    ans = dp[N][loop-1]
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
            W %= mod
            B %= mod
#        print(s,W,B)
        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%mod)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examO()

"""

"""

Submission status: Accepted

Solution code:
DIV = 10**9+7

N = int(input())
a = []
for i in range(N):
  a.append(list(map(lambda x: int(x), input().split())))
  
#dp[i][b] = i番目でビット列bに到達するパターン数
dp = [[0]*(2**N) for i in range(N)]
#dp[0][:]の初期化
for k in range(N):
  if a[0][k]==1:
    dp[0][(1<<k)] = 1
    
for i in range(1, N):
  for b in range(2**N):
    if dp[i-1][b]==0:
      continue
    for k in range(N):
      if a[i][k]==1 and b&(1<<k)==0:
        target = (b|(1<<k))
        dp[i][target] += dp[i-1][b]
        if dp[i][target]>DIV:
          dp[i][target] %= DIV
          
s = 0
for i in range(2**N):
  s += dp[N-1][i]
  if s>DIV:
    s %= DIV
    
print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
ans = [0]*(1<<n)
ans[0] = 1
mod = 10**9 + 7

def popcnt(x):
  ret = 0
  for i in range(n):
    if x & (1<<i):
      ret += 1
  return ret

for bit in range(1<<n):
  if ans[bit]:
    i = popcnt(bit)
    v = 1
    for j in range(n):
      if not bit & v and a[i][j]:
        ans[bit|v] = (ans[bit|v] + ans[bit])%mod
      v <<= 1
print(ans[-1])

Submission status: Accepted

Solution code:
def main():

    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]

    MOD = 10**9 +7
    dp = [0] * (1<<n)

    pair_dic = {}
    for i in range(n+1):
        pair_dic[i] = []

    for i in range(1<<n):
        pair_dic[ bin(i).count('1') ].append(i)

    dp[0] = 1

    for i in range(n):
        for k in range(n):
            if(a[i-1][k] == 0):
                continue
            for j in pair_dic[i]:
                if(  ((j&(1<<k)) >>k == 0 ) ):
                    dp[j + (1<<k)] += dp[j]
                    dp[j + (1<<k)] = dp[j + (1<<k)] % MOD

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, = map(int, input().split())
M=10**9+7
n=N
_ALL=1<<n
def itercomb(n,k):
    if k==0:
        yield 0
    else:
        _a = (1<<k)-1
        yield _a
        while 1:
            _x = _a & -_a
            _y = _a + _x
            _a = (((_a & ~_y) // _x) >> 1) | _y
            if _a >= _ALL: break
            yield _a


xs = []
for _ in range(N):
    xs.append([1<<i for i, x in enumerate(input().split()) if int(x)])
d = [0]*(1<<N)
d[0] = 1
for i, y in enumerate(xs):
    for x in itercomb(N, i):
        for ai in y:
            if (not x&ai):
                d[x|ai] = (d[x] + d[x|ai])%M
print(d[-1])

Submission status: Accepted

Solution code:
N, = map(int, input().split())
M=10**9+7
n=N
_ALL=1<<n
def itercomb(n,k):
    if k==0:
        yield 0
    else:
        _a = (1<<k)-1
        yield _a
        while 1:
            _x = _a & -_a
            _y = _a + _x
            _a = (((_a & ~_y) // _x) >> 1) | _y
            if _a >= _ALL: break
            yield _a


xs = []
for _ in range(N):
    xs.append([1<<i for i, x in enumerate(input().split()) if int(x)])
d = [0]*(1<<N)
d[0] = 1
for i, y in enumerate(xs):
    for x in itercomb(N, i):
        for ai in y:
            if (not x&ai):
                d[x|ai] += d[x]%M
                if d[x|ai] >M:
                    d[x|ai]-=M
print(d[-1])

Submission status: Accepted

Solution code:
mod = 10**9+7

n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]

dp = [-1 for __ in range(1 << n)]
dp[0] = 1


def dfs(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]


print(dfs(2**n-1, 0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def bit(n, k):
    return (n >> k) & 1


def solve(N: int, a: "List[List[int]]"):
    dp = [0]*(1 << N)
    dp[0] = 1
    for S in range(1, 1 << N):
        i = bit_sum(S)
        for j in range(N):
            if bit(S, j) == 1 and a[i-1][j] == 1:
                dp[S] = (dp[S]+dp[S ^ (1 << j)]) % MOD
    print(dp[(1 << N)-1])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [[int(next(tokens)) for _ in range(N)]
         for _ in range(N)]  # type: "List[List[int]]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
MOD = 10**9 + 7

dp = [[0] * (1 << n) for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    bit_state = (1 << i) - 1
    if bit_state == 0:
        for j in range(n):
            if not(bit_state & (1 << j)) and a[i][j] == 1:
                dp[i+1][bit_state|(1 << j)] += dp[i][bit_state]
                dp[i+1][bit_state|(1 << j)] %= MOD
        continue
    while bit_state < (1 << n):
        for j in range(n):
            if not(bit_state & (1 << j)) and a[i][j] == 1:
                dp[i+1][bit_state|(1 << j)] += dp[i][bit_state]
                dp[i+1][bit_state|(1 << j)] %= MOD
        x = bit_state & -bit_state
        y = bit_state + x
        bit_state = ((bit_state & ~y) // x >> 1) | y
print(dp[n][(1 << n) - 1])

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]

mod = 10**9+7

dp = [0]*(2**N)
dp[0] = 1

POPCOUNT_TABLE16 = [0] * 2**16
for index in range(len(POPCOUNT_TABLE16)):
    POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcnt(v):
    return (POPCOUNT_TABLE16[ v        & 0xffff] +
            POPCOUNT_TABLE16[(v >> 16) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 32) & 0xffff] +
            POPCOUNT_TABLE16[(v >> 48)         ])


for s in range(1, 2**N):
    i = popcnt(s)
    cnt = 0
    for j in range(N):
        if A[i-1][j] == 1 and s&(1<<j):
            cnt += dp[s^(1<<j)]%mod
    dp[s] = cnt%mod
            
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    adj = []
    for i in range(N):
        adj.append(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    state_list = [[] for _ in range(N + 1)]
    for state in range(2 ** N):
        one_num = 0
        for j in range(N):
            if state >> j & 1:
                one_num += 1
        state_list[one_num].append(state)

    dp = [0] * (2**N)
    dp[0] = 1
    for i in range(N):
        for j in range(N):
            if adj[i][j]:
                for state in state_list[i]:
                    state_new = state | (2**j)
                    if state != state_new:
                        dp[state_new] += dp[state]
                        if dp[state_new] >= mod:
                            dp[state_new] -= mod

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    adj = []
    for i in range(N):
        adj.append(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    state_list = [[] for _ in range(N + 1)]
    for state in range(2 ** N):
        one_num = 0
        for j in range(N):
            if state >> j & 1:
                one_num += 1
        state_list[one_num].append(state)

    dp = [0] * (2**N)
    dp[0] = 1
    for i in range(N):
        for j in range(N):
            if adj[i][j]:
                for state in state_list[i]:
                    state_new = state | (2**j)
                    if state != state_new:
                        dp[state_new] = (dp[state_new] + dp[state]) % mod

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = int(1e9 + 7)

n = int(input())
can = []
for _ in range(n):
    can.append([int(c) for c in input().split()])

dp = [0] * (2 ** n)
dp[0] = 1

for mask in range(2 ** n - 1):
    a = bin(mask).count('1')
    for b in range(n):
        if can[a][b] and not(mask & (1 << b)):
            m2 = mask ^ (1 << b)
            dp[m2] = dp[m2] + dp[mask]
            if dp[m2] > MOD:
                dp[m2] -= MOD


print(dp[(2**n) - 1])

Submission status: Accepted

Solution code:
def bitcount(i): # i < 2^32
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

MOD = 10**9+7
n = int(input())
can = [[int(i) for i in input().split()] for j in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
for mask in range((1 << n) - 1):
    a = bin(mask).count('1')
    #a = bitcount(mask)
    for b in range(n):
        if can[a][b] and not (mask & (1 << b)):
            mask2 = mask ^ (1 << b)
            dp[mask2] += dp[mask]
            if dp[mask2] >= MOD:
                dp[mask2] -= MOD
print(dp[(1 << n) - 1])

Submission status: Accepted

Solution code:
def bitcount(i): # i < 2^32
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

MOD = 10**9+7
n = int(input())
can = [[int(i) for i in input().split()] for j in range(n)]
dp = [0] * (1 << n)
dp[0] = 1
for mask in range((1 << n) - 1):
    #a = bin(mask).count('1')
    a = bitcount(mask)
    for b in range(n):
        if can[a][b] and not (mask & (1 << b)):
            mask2 = mask ^ (1 << b)
            dp[mask2] += dp[mask]
            if dp[mask2] >= MOD:
                dp[mask2] -= MOD
print(dp[(1 << n) - 1])

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(1<<N)
    dp[0] = 1
    def bitcount(i): # i < 2^32
        i = i - ((i >> 1) & 0x55555555)
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
        return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
    for s in range(1, 1<<N):
        women = []
        m = bitcount(s)-1
        for w in range(N):
            if a[m][w] == 1 and s&1<<w:
                dp[s]+=dp[s^(1<<w)]
                dp[s]%=mod
    print(dp[-1])
main()

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
def bitcount(i): # i < 2^32
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
for s in range(1, 1<<N):
    women = []
    m = bitcount(s)-1
    for w in range(N):
        if a[m][w] == 1 and s&1<<w:
            dp[s]+=dp[s^(1<<w)]
            dp[s]%=mod
print(dp[-1])

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
for s in range(1, 1<<N):
    women = []
    for i in range(N):
        if (1<<i)&s:
            women.append(i)
    m = len(women)-1
    for w in women:
        if a[m][w] == 1:
            dp[s]+=dp[s^(1<<w)]
            dp[s]%=mod
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(_) for _ in input().split()] for i in range(N)]

dp = [[0] * ((1 << 21) + 10) for _ in range(N + 1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(N):
    # i 番目の男性に着目
    for s in range(1 << N):  # sのbit が立っている女子はマッチ済み
        if dp[i][s] == 0: continue

        for j in range(N):
            jb = 1 << j
            if not (s & jb) and A[i][j]:
                # i, j をマッチさせる
                dp[i + 1][s | jb] += dp[i][s]
print(dp[N][(1 << N) - 1] % MOD)

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(_) for _ in input().split()] for i in range(N)]

dp = [[0] * ((1 << 21) + 10) for _ in range(N + 1)]
dp[0][0] = 1
MOD = 10**9+7
for i in range(N):
    # i 番目の男性に着目
    for s in range(1 << N):  # sのbit が立っている女子はマッチ済み
        if dp[i][s] == 0: continue

        for j in range(N):
            jb = 1 << j
            if not (s & jb) and A[i][j]:
                # i, j をマッチさせる
                dp[i + 1][s | jb] += dp[i][s] % MOD
print(dp[N][(1 << N) - 1] % MOD)

Submission status: Accepted

Solution code:
def solve(n, a):
    mod = 10 ** 9 + 7

    dp = [0] * (1 << n)
    # dp[ペアになった女の集合] = 状態数
    dp[0] = 1

    for mask in range(1, 1 << n):
        man = bin(mask).count('1') - 1
        for woman in range(n):
            if (mask >> woman) & 1 == 1 and a[man][woman] == 1:
                dp[mask] = (dp[mask] + dp[mask & ~(1 << woman)]) % mod

    return dp[(1 << n) - 1]


if __name__ == '__main__':
    n = int(input())
    a = tuple(tuple(map(int, input().split())) for _ in range(n))
    print(solve(n, a))