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: Wrong Answer

Solution code:
# read the input
n = int(input())
preference = []
for _ in range(n):
    preference.append(list(map(int, input().strip().split())))

# initialization
noStates = 2 ** n
mod = 10 ** 9 + 7
dp = [[None for _ in range(noStates)] for _ in range(n+1)]

# computing
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(noStates):
        if dp[i - 1][j] is None:
            continue

        if dp[i][j] is None:
            dp[i][j] = dp[i - 1][j]

        for k in range(n):
            if preference[i - 1][k] and (j & (2 ** k)) == 0:
                target = j | (2 ** k)
                if dp[i][target] is None:
                    dp[i][target] = 0

                dp[i][target] += dp[i - 1][j]
                dp[i][target] %= mod

print(dp[n][noStates - 1])

Submission status: Wrong Answer

Solution code:
n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(1<<j)]


print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    table = [na() for _ in range(n)]

    dp = [0 for _ in range(2 ** n)]
    dp[2 ** n - 1] = 1

    for i in range(2 ** n - 1, 0, -1):
        j = n - format(i, "b").count("1")
        for j, val in enumerate(table[j]):
            if val:
                if i & 1 << j:
                    dp[i ^ 1 << j] += dp[i]

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
    
dp = [[0]*pow(2,n) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    comb = (1<<(i)) - 1
    while comb < 1 << n:
        # ここに処理
        for j in range(n):
            if comb>>j and a[i-1][j]:
                dp[i][comb] += dp[i-1][comb-(1<<j)]
        x = comb & (-comb); y = comb + x
        comb = (((comb&~y) // x )>>1) | y
print(dp[n][pow(2,n)-1])

Submission status: Wrong Answer

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

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

# 配るDP
for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        if a[i][j]:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

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

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if a[i][j] and ~((bit >> j) & 1):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

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

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if a[i][j] and not((bit >> j) | 0):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

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

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        newbit = bit | (1 << j)
        if a[i][j] and (bit >> j) & 0:
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

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

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        if a[i][j] and (bit >> j) & 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Wrong Answer

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

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

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

for bit in range(1,1 << n):
    i = bin(bit).count('1')
    for j in range(n):
        if ((bit >> j) & 1 == 0) and (a[i - 1][j] == 1):
            oldbit = bit ^ (1 << j)
            dp[bit] += dp[oldbit]
            dp[bit] %= mod
print(dp[-1])

Submission status: Wrong Answer

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

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

for bit in range((1 << n) - 1):
    i = bin(bit).count('1')
    for j in range(n):
        if a[i][j] and (bit >> j) & 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# bit DP...?
dp = [[0] * (2 ** n) for i in range(n + 1)]
dp[0][0] = 1

bitcal = sorted([pow(2, i) for i in range(n)], reverse=True)
bitlist = [[i] for i in range(n)]  # 1が少ない順に作りたい...
for i in range(1, n):
    bitlist.extend(combinations(range(n), i + 1))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# bit DP...?
dp = [[0] * (2 ** n) for i in range(n + 1)]
dp[0][0] = 1

bitcal = sorted([pow(2, i) for i in range(n)], reverse=True)
bitlist = [[i] for i in range(n)]  # 1が少ない順に作りたい...
for i in range(1,n):
    bitlist = bitlist + list(combinations(range(n), i + 1))

Submission status: Wrong Answer

Solution code:
from itertools import product

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

# bit DP...?
dp = [[0] * n for i in range(2 ** n)]
list = sorted([[sum(i), i] for i in product([0, 1], repeat=n)])

for i, j in list:
    #for bit in str(j).split():
        #print(bit)
        #if bit == 1:
            #pass
            # dp[i][num] += dp[i - 1][] * a[i][]
    pass
print(list)

Submission status: Wrong Answer

Solution code:
n  =int(input())

comp = []
for i in  range(n):
    temp = [int(x) for x in input().split()]
    temp2= []
    for j,e in enumerate(temp):
        if e == 1:
            temp2.append(j)
    comp.append(temp2)

# n -> 21
from functools import lru_cache
target = 1 << n -1
@lru_cache(None)
def make_pair(mask,women_num):
    if mask == target:
        return 1
    
    ans = 0
    for bit in range(n):
        if mask >> bit & 1 == 0:
            for women in comp[bit]:
                if women > women_num:
                    ans += make_pair(mask | 1 << bit,women)
    return ans
MOD = 10**9+7
print(make_pair(0,-1)%MOD)

Submission status: Wrong Answer

Solution code:
# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
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
for i in range(1,1<<n):
    k=bin(i).count("1")
    # k-1人目までは確定
    for j in range(n):
        if i>>j&1 and a[k-1][j]:
            dp[i]+=dp[i^(1<<j)]
    dp[i]%=mod
print(dp)
print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
#bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
mod=10*9+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    k=bin(i).count("1")
    for j in range(n):
        if i>>j&1 and a[k-1][j]:
            dp[i]=(dp[i]+dp[i^(1<<j)])%mod
print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
def main():
  n = int(input())
  a = []
  for i in range(n):
    a.extend(list(map(int,input().split())))
  dp = [0]*(1<<n)
  dp[0] = 1
  for S in range((1<<n)-1):
    k = bin(S).count("1")*n
    t = dp[S]
    if t:
      for i in range(n):
        if a[k+i]:
          dp[S|1<<i] = (dp[S|1<<i]+t)%mod
    print(dp[(1<<n)-1])
main()

Submission status: Wrong Answer

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)]
print(dp[-1])

Submission status: Wrong Answer

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 << N) - 1):
    i = 0
    for j in range(N):
        if bit >> j & 1 == 1:
            i += 1
    for j in range(N):
        if a[i][j] == 1 and bit >> j & 1 == 0:
            dp[bit | (1 << j)] += dp[bit]
print(dp[-1])

Submission status: Wrong Answer

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
    q = deque()
    q.append((0, 0))
    while q:
        p, i = q.popleft()
        for j in range(n):
            if a[i][j]:
                j1 = 1 << j
                if p & j1:
                    continue
                pj1 = p | j1
                q.append((pj1, j))
                dp[pj1] += dp[p]
                if dp[pj1] >= mod:
                    dp[pj1] %= mod
    print(dp[-1])


    return


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

Submission status: Wrong Answer

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):
    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])
print(*dp,sep="\n")

Submission status: Wrong Answer

Solution code:
from itertools import combinations

N, = map(int, input().split())
xs = []
ss = [2**i for i in range(N)]
for _ in range(N):
    xs.append([1<<i for i, x in enumerate(input().split()) if int(x)])
M=10**9+7
d = [0]*(1<<N)
d[0] = 1
for i, x in enumerate(xs):
    for ai in x:
        for j in combinations(ss, i):
#            x = sum(j)
            x=0
            if (not x&ai):
                d[x|ai] = (d[x|ai]+d[x])%M
print(d[-1])

Submission status: Wrong Answer

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

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

for bit in range(1 << n):
    i = bin(bit).count("1")
    for j in range(n):
        if a[i-1][j] == 1 and (bit & 1 << j):
            dp[bit] += dp[bit ^ (1 << j)]

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations,product
p = 10**9+7
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
G = {i:[] for i in range(N)}
for i in range(N):
    for j in range(N):
        if A[i][j]==1:
            G[i].append(j)
Gb = {i:[0 for _ in range(N)] for i in range(N)}
for i in range(N):
    for j in G[i]:
        Gb[i][j] = 1
dp = {x:[0 for _ in range(N)] for x in product((0,1),repeat=N)}
for z in combinations(range(N),N-1):
    x = tuple([1 if i in z else 0 for i in range(N)])
    for j in G[N-1]:
        if x[j]==0:
            dp[x][N-1] = 1
for i in range(N-2,-1,-1):
    for z in combinations(range(N),N-i):
        for j in z:
            if Gb[i][j]==1:
                y = [0 if j in z else 1 for j in range(N)]
                y[j] = 1
                y = tuple(y)
                dp[x][i] = (dp[x][i]+dp[y][i+1])%p
s = tuple([0 for _ in range(N)])
print(dp[s][0])

Submission status: Wrong Answer

Solution code:
N = int(input())
compat = [list(map(int, input().split())) for i in range(N)]

MOD = int(pow(10, 9) + 7)
# dp[i][j] = first i men have been paired, j bitmask of women
dp = [[-1 for i in range(1 << N)] for j in range(N + 1)]
dp[0][0] = 1

count = 0
def recurse(num, free):
    if num == 0:
        return 1
    if dp[num][free] != -1:
        return dp[num][free]
    total = 0
    for i in range(N):
        if compat[num-1][i] and free & (1 << i):
            total += recurse(num - 1, free & ~(1 << i))
    total %= MOD
    dp[num][free] = total
    return total

recurse(N, (1 << N) - 1)
print(dp[-1][-1])
print(count)

Submission status: Wrong Answer

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
for i in range(N):
    # i 番目の男性に着目
    for s in range(1 << N):  # sのbit が立っている女子はマッチ済み
        if dp[i][s] == 0: continue
        s2 = s
        bcnt = 0
        while s2 > 0:
            if s2 & 1: bcnt += 1
            s2 = s2 >> 1
        if s2 >= i + 1: break

        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])

Submission status: Wrong Answer

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
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])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

MOD = 1e9+7

n = int(input())
a = [[0]*n for i in range(n)]

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

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

# sys.exit(0)

def solve(i, mask):
    if (i==n):
        return 1

    if (dp[i][mask]!=-1):
        return dp[i][mask]
    
    ans = 0
    for j in range(n):
        if a[i][j]==1 and (mask&(1<<j))==0:
            ans = (ans+solve(i+1, mask|(1<<j)))%MOD

    dp[i][mask]=ans
    return ans

print(solve(0, 0))

Submission status: Wrong Answer

Solution code:
# @author 

import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        def numberOfSetBits(i):
            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())
        a = []
        for i in range(n):
            a.append([int(_) for _ in input().split()])


        dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        by_1 = defaultdict(list)
        for j in range(1 << n):
            by_1[numberOfSetBits(j)].append(j)
        for j in range(1 << n):
            by_1[bin(j).count('1')].append(j)

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

        # [print(item) for item in dp]

        print(sum(dp[n]))

solver = OMatching()
input = sys.stdin.readline

solver.solve()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

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

for m in range(1,n+1):
    a = 1<<m-1
    while a < _ALL:
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD
        x = a & -a
        y = a + x
        a = (((a & ~y) // x) >> 1) | y

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

Submission status: Wrong Answer

Solution code:
"""
O - Matching

考え方:
    1 ～ 2^N までの数値を用意し, それぞれの状態を 1 ～ b' 番目までの男性がマッチング完了した状態と定義する.
    この時, b' は n' を2進数で表した時の 1 bit の和とする.
    また, n' の i 桁目のビットが 1 であれば i 番目の女性はマッチング済みとする.
    ここで n' の状態が X 件成立する場合, n'' = b' + 1 を満たすすべての n に対して, n' から新たに増えたビット部分の女性とマッチングが可能であれば n'' でも X 成立するといえる.
    これを連続して計算することで最終的にすべての男女がマッチングする組み合わせの件数が求められる.

"""


def solve():
    # データ読込
    N = int(input())
    compatibility = [[int(i) for i in input().split()] for _ in range(N)]
    # dp のデータ格納用配列の作成
    dp = [0] * (2 ** N)  # 初期値は 0(件)
    # print(len(dp))
    # 配列をループ
    for i in range(1, len(dp) - 1):
        man_num = bin(i).count('1')
        # 男性一人の場合は初期値設定
        if man_num == 1:
            for j in range(N):
                if (i >> j) % 2 == 1:
                    dp[i] = compatibility[man_num - 1][j]
                    break
        # 現状に1組追加したパターンに組み合わせ数を追加
        if dp[i] == 0: continue
        for j in range(N):
            if (i >> j) % 2 != 1:
                if compatibility[man_num][j] == 1:
                    dp[i | 2 ** j] += dp[i]
        # print(bin(i))
        # print(dp[1:])

    # 結果出力
    # print(dp[1:])
    print(dp[-1] % (10 ** 9 + 7))
    pass


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
A=[list(map(int,input().split()))for _ in[0]*n]
p=[0]*2**n
p[0]=1
for I in range(2**n-1):
 a=A[bin(I).count('1')]
 for j in range(n):
  if a[j]:p[I|1<<j]+=p[I]
print(p[-1]%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# read the input
from functools import lru_cache

n = int(input())
preference = []
for _ in range(n):
    preference.append(list(map(int, input().strip().split())))

# initialization
noStates = 2 ** n
mod = 10 ** 9 + 7


@lru_cache(None)
def compute(idx, state):
    if idx == n - 1:
        for i in range(n):
            if state & (2 ** i) == 0:
                return preference[idx][i]
    res = 0
    for i in range(n):
        if state & (2 ** i) == 0 and preference[idx][i]:
            res += compute(idx + 1, state | (2 ** i))

    return res % mod


print(compute(0, 0))

Submission status: Time Limit Exceeded

Solution code:
# read the input
n = int(input())
preference = []
for _ in range(n):
    preference.append(list(map(int, input().strip().split())))

# initialization
noStates = 2 ** n
mod = 10 ** 9 + 7
dp = [[None for _ in range(noStates)] for _ in range(n)]


def compute(idx, state):
    if dp[idx][state] is not None:
        return dp[idx][state]

    if idx == n - 1:
        for i in range(n):
            if state & (2 ** i) == 0:
                dp[idx][state] = preference[idx][i]
                return preference[idx][i]
    res = 0
    for i in range(n):
        if state & (2 ** i) == 0 and preference[idx][i]:
            res += compute(idx + 1, state | (2 ** i))

    dp[idx][state] = res % mod
    return dp[idx][state]


print(compute(0, 0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    e=bin(i)[2:]
    y=e.count('1')
    for j in range(len(e)):
        if e[-j-1]=='1':
            if g[y-1][j]:
                    dp[i]+=dp[i-(1<<j)]
                    dp[i]%=mod


print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
dp = {}
mod = 10**9+7
def getAns(st, wom, comp, n):
    if wom == 0 and st >= n:
        return 1 
    if wom > 0 and st >= n:
        return 0
    
    if (st,wom) in dp:
        return dp[(st,  wom)]

    ans = 0
    for i in range(n):
        if comp[st][i] == 1 and (1<<i & wom):
            ans = (ans+getAns(st+1, wom^(1<<i), comp, n))%mod
    
    dp[(st, wom)] = ans
    return ans






n = int(input())
comp = [list(map(int, input().strip().split())) for i in range(n)]
 
print(getAns(0, (1<<n)-1, comp, n))

Submission status: Time Limit Exceeded

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

def dp(p,v):
    if p==n:
        return 1
    k=0
    
            
    for j in range(n):
        if g[p][j]==1 and (v>>j)&1==1:
            #print(p,j)

            
            k+=dp(p+1,v^(1<<j))
            k%=mod
            #print(vw)

            
                    
    return k%mod


print(dp(0,(1<<n)-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))
mod=10**9+7
def dp(p,vw):
    if p==n:
        return 1
    k=0
    
            
    for j in range(n):
        if g[p][j]==1 and vw[j]==0:
            #print(p,j)

            vw[j]=1
            k+=dp(p+1,vw)
            k%=mod
            #print(vw)

            vw[j]=0
                    
    return k%mod

viw=[0]*n
print(dp(0,viw))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
g=[]
for i in range(n):
    
    g.append(list(map(int,input().split())))

def dp(p,vw):
    if p==n:
        return 1
    k=0
    
            
    for j in range(n):
        if g[p][j]==1 and vw[j]==0:
            #print(p,j)

            vw[j]=1
            k+=dp(p+1,vw)
            #print(vw)

            vw[j]=0
                    
    return k

viw=[0]*n
print(dp(0,viw))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

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

for m in Match:
    D = DP[:]
    for i, d in enumerate(DP):
        if d:
            for j in range(N):
                if (m >> j) & 1 == 1:
                    if (i >> j) & 1 == 0:
                        D[i| (1 << j)] += d
                        D[i| (1 << j)] %= mod
    DP = D
print(DP[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

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

for m in Match:
    D = DP[:]
    for i, d in enumerate(DP):
        for j in range(N):
            if (m >> j) & 1 == 1:
                if (i >> j) & 1 == 0:
                    D[i| (1 << j)] += d
                    D[i| (1 << j)] %= mod
    DP = D
print(DP[-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

dp=[0]*(2**n)
dp[0]=1
visited=[False]*(2**n)
visited[0]=True

for i in range(1,n+1):
    for lst in itertools.permutations(['1']*i+['0']*(n-i),n):
        lst2=''.join(lst)
        if visited[int(lst2,base=2)]:
          continue
        visited[int(lst2,base=2)]=True

        for j in range(n):
            if lst[-j-1]=='1':
                if a[i-1][j]==1:
                    dp[int(lst2,base=2)]+=dp[int(lst2,base=2)-2**j]
                    dp[int(lst2,base=2)]%=mod



print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
dp = [[0]*(1<<n) for _ in range(n+1)]
dp[0][(1<<n)-1] = 1
for i in range(n):
  for j in range(n):
    for k in range(1<<n):
      if A[i][j] and (k>>j & 1):
        dp[i+1][k^(1<<j)] += dp[i][k]
        dp[i+1][k^(1<<j)] %= mod
ans = dp[n][0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce

N = a_int()
A = read_matrix(N, N)

'''
一方の集合を管理してDPというアイデア

dp[i][s] ... 男性を:i人目まで見たときに、マッチングした女性の集合がsであるような通りの総数

更新式
dp[i+1][s+1<<j] += dp[i][s] for s のjbit目は0 かつ A[i,j]==1

これでは計算量がO(2^N 2N)なのでTLE
iと|s|は同じなのだから状態をまとめることができる
(二次元dpでいうとi=|s|のセルでしか状態遷移が発生しない)

よって単純sだけでループしても良さそうだし、()内のアイデアで枝刈りしても良さそう
'''

from numba import njit


@njit('(i8,i8[:,:])', cache=True)
def solve_TLE(N, A):
    dp = np.zeros((N + 1, 1 << N), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        for s in range(1 << N):
            for j in range(N):
                if (s >> j) & 1 == 0 and A[i, j] == 1:
                    dp[i + 1, s + (1 << j)] += dp[i, s] % MOD
    print(dp[N, (1 << N) - 1] % MOD)


solve_TLE(N, A)