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: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
A = [[j for j in range(n) if A[i][j]] for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in A[l-1]:
        if (1 << i) & s:
            DP[s] = (DP[s]+DP[~(1 << i) & s]) % p
print(DP[(1 << n)-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
A = [[j for j in range(n) if A[i][j]] for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in A[l-1]:
        if ((1 << i) & s):
            DP[s] += DP[~(1 << i) & s]
            DP[s] %= p
print(DP[(1 << n)-1])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    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):
        i = popcount(bin(S))
        for j in range(N):
            if (S >> j) & 1 and a[i-1][j] == 1:
                dp[S] = dp[S]+dp[S^(1<<j)]
                dp[S] %= MOD

    print(dp[(1<<N)-1])

def popcount(bit):
    cnt = 0
    for b in bit:
        if b == '1':
            cnt += 1
    return cnt
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
                DP[s] %= p
    print(DP[(1 << n)-1])


main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in range(n):
        if ((1 << i) & s) * A[l-1][i]:
            DP[s] += DP[~(1 << i) & s]
print(DP[(1 << n)-1]%p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [0 for s in range(1 << n)]
DP[0] = 1
for s in range(1, 1 << n):
    l = bin(s).count('1')
    for i in range(n):
        if ((1 << i) & s) * A[l-1][i]:
            DP[s] += DP[~(1 << i) & s]
            DP[s] %= p
print(DP[(1 << n)-1])

Submission status: Time Limit Exceeded

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):
    for j in range(n):
        k=bin(i).count("1")
        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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  mod = 10**9+7
  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: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  mod = 10**9+7
  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]
    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: Time Limit Exceeded

Solution code:
def c(S):
    cnt = 0
    for i in range(len(bin(S))-2):
        cnt += S>>i&1
    return cnt
mod = 10**9+7
N = int(input())
li = [list(map(int, input().split())) for i in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
for S in range(1, 1<<N):
    num = c(S)
    for i in range(N):
        if S>>i&li[num-1][i] == 1:
            dp[S] = (dp[S]+dp[S-(1<<i)]) %mod
print(dp[(1<<N)-1])

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

B = 2**N
dp = [0]*B
dp[B-1] = 1

bit = [[] for _ in range(N+1)]
for v in list(itertools.product([0,1], repeat=N)):
    s = sum(v)
    b = int("".join(list(map(str, v))), 2)
    bit[s].append(b)

for not_matched_woman in reversed(range(1,N+1)):
    for b in bit[not_matched_woman]:
        for i in [i for i in range(N) if A[not_matched_woman-1][i]]:
            if b & (1 << i):
                dp[b ^ (1 << i)] += dp[b]
                dp[b ^ (1 << i)] %= MOD

print(dp[0])

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [[int(_) for _ in input().split()] for _ in range(N)]
MOD = 10**9+7

dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for s in range(1<<N):
        if dp[i][s] == 0:continue
        for j in range(N):
            jb = 1<<j
            if not (s&jb) and a[i][j]:
                dp[i+1][s|jb] += dp[i][s]
    
print(dp[N][(1<<N)-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [[int(_) for _ in input().split()] for _ in range(N)]
MOD = 10**9+7

dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    for s in range(1<<N):
        if dp[i][s] == 0:
            continue
        for j in range(N):
            jb = 1<<j
            if not (s&jb) and a[i][j]:
                dp[i+1][s|jb] += dp[i][s]
    
print(dp[-1][(1<<N)-1]%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [[int(_) for _ in input().split()] for _ in range(N)]
MOD = 10**9+7

dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    use = [0 for _ in range((1<<N)+1)]
    for s in range(1<<N):
        if dp[i][s] == 0:
            continue
        for j in range(N):
            jb = 1<<j
            if not (s&jb) and a[i][j]:
                dp[i+1][s|jb] += dp[i][s]
    
print(dp[-1][(1<<N)-1]%MOD)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = [[int(_) for _ in input().split()] for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0 for _ in range((1<<N)+1)] for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
                    use[s^jb] %= MOD
        dp = use
    
    print(dp[(1<<N)-1])
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations as combi
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 t in range(N):
  for c in combi([x for x in range(N)], t):
    x = 0
    for i in c: x += 1 << i
    s = set(c)
    for i in range(N):
      if i in s: continue
      if a[t][i]:
        dp[x + (1 << i)] += dp[x]
        dp[x + (1 << i)] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(input())

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

dp = [-1] * (1 << N)
dp[(1 << N) - 1] = 1

def dfs(group, count):
    if dp[group] != -1:
        return dp[group]
    res = 0
    for i in range(N):
        if (group >> i) & 1 == 0 and A[count][i] == 1:
            res += dfs(group + (1 << i), count + 1)
    dp[group] = res % MOD
    return dp[group]

tmp = dfs(0, 0)

print (tmp)

Submission status: Time Limit Exceeded

Solution code:
#bitDP(再帰使用)
#forの組合せでやろうとすると男性の集合/女性の集合を分けるのが難しい

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

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

    #dp[s]：sは既に使った女性をbitで表していて、
    #          dp[s]は残りの男女の組合せの場合の数
    dp = [-1]*(1<<N)
    #全員相手が見つかった状態
    dp[-1] = 1

    #numは今見ている男性
    def dfs(s, num):
        #既にその状態を調べ終わっているなら返す
        if dp[s] != -1:
            return dp[s]

        #resは状態(s, num)において考えられる場合の数で
        #for文で全ての女性について考えて足している
        res = 0

        #状態sにおいて, 男性numと全ての女性とのマッチングを考える
        for i in range(N):
            #i番目の女性がまだ使っていなくて, 今見ている男性と相性が良い時
            if(s >> i) & 1 == 0 and a[num][i] == 1:
                #sを更新して, 次の男性について調べる
                #次の状態が既に調べ終わっていたらその場合の数が足される
                res += dfs(s+(1<<i), num+1)
        dp[s] = res % mod
        return dp[s]

    print(dfs(0, 0))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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}
for B in A:
    nxt = Counter()
    C = [1 << i for i, v in enumerate(B) if v == 1]
    for s, v in cur.items():
        v %= M
        for b in C:
            if (s & b) != 0:
                continue
            m = s | b
            nxt[m] += v
    cur = nxt
print(cur[(1<<N) - 1] % M)

Submission status: Time Limit Exceeded

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}
for B in A:
    nxt = Counter()
    C = [1 << i for i, v in enumerate(B) if v == 1]
    for s, v in cur.items():
        for b in C:
            if (s & b) != 0:
                continue
            m = s | b
            nxt[m] += v
            nxt[m] %= M
    cur = nxt
print(cur[(1<<N) - 1])

Submission status: Time Limit Exceeded

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

def fm(array):
    return ["*" if v is None else v for v in array]

def bitcount(v):
    cnt = 0
    for i in range(n):
        cnt += bool(v & (1 << i))
    return cnt

ok = (1 << n) - 1

dp = [None] * (1 << n)
def dfs(state=0):
    if dp[state] is not None:
        return dp[state]

    if state == ok:
        dp[state] = 1
        return 1
    cnt = 0
    i = bitcount(state)
    for index, v in enumerate(a[i]):
        p = 1 << index
        if v and not state & p:
            cnt += dfs(state + p)
    dp[state] = cnt
    return cnt

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

for state in reversed(range(1 << n)):
    if state == ok:
        dp[state] = 1
        continue
    cnt = 0
    i = bitcount(state)
    for index, v in enumerate(a[i]):
        p = 1 << index
        if v and not state & p:
            cnt = mod(cnt + dp[state + p])
    dp[state] = mod(cnt)

print(mod(dp[0]))

Submission status: Time Limit Exceeded

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

def fm(array):
    return ["*" if v is None else v for v in array]

ok = (1 << n) - 1

dp = [[None] * (1 << n) for _ in range(n + 1)]
def dfs(i=0, state=0):
    if dp[i][state] is not None:
        return dp[i][state]

    if i == n:
        r = int(state == ok)
        dp[i][state] = r
        return r
    cnt = 0
    for index, v in enumerate(a[i]):
        p = 1 << index
        # if v and not state & p:
        #     cnt += dfs(i + 1, state | p)
        if not state & p:
            cnt += dfs(i + 1, state | p) * v
    dp[i][state] = cnt
    return cnt

print(dfs())

# for v in dp:
#     print(*fm(v))

Submission status: Time Limit Exceeded

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)]
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[-1])

Submission status: Time Limit Exceeded

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
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = 1 << j
        for s in prev:
            dp[s] %= MOD
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N = int(input())
dp = [0] * (1 << N)
dp[0] = 1
prev = [0]
for i in range(N):
    temp = []
    for bit in [1 << i for i, v in enumerate(input().split()) if v == '1']:
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

Submission status: Time Limit Exceeded

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
prev = [0]
for i, a in enumerate(A):
    temp = []
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

Submission status: Time Limit Exceeded

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
prev = {0}
for i in range(N):
    temp = set([])
    for j in range(N):
        if A[i][j] != 1: continue
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp |= {new_s}
    prev = temp
print(dp[(1 << N) - 1])

Submission status: Time Limit Exceeded

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
prev = [0]
for i in range(N):
    temp = []
    for j in range(N):
        if A[i][j] != 1: continue
        bit = 1 << j
        for s in prev:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
                temp.append(new_s)
    prev = list(set(temp))
print(dp[(1 << N) - 1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (1 << N) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        if A[i][j] != 1: continue
        bit = 1 << j
        for s in range(1 << N):
            if s & bit == 0:
                new_s = s | bit
                dp[i+1][new_s] += dp[i][s]
                dp[i+1][new_s] %= MOD
print(dp[N][(1 << N) - 1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 = [[0], []]
    b = [1 << i for i in range(n)]
    for i in range(n):
        t = i & 1
        t1 = t ^ 1
        i1 = i + 1
        ai = a[i]
        while q[t]:
            p = q[t].pop()
            for j in range(n):
                if ai[j]:
                    j1 = b[j]
                    if p & j1:
                        continue
                    pj1 = p | j1
                    dp[pj1] += dp[p]
                    if i1 == n: continue
                    q[t1].append(pj1)

    print(dp[-1] % mod)


    return


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

Submission status: Time Limit Exceeded

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()
        ai = a[i]
        i1 = i + 1
        for j in range(n):
            if ai[j]:
                j1 = 1 << j
                if p & j1:
                    continue
                pj1 = p | j1
                dp[pj1] += dp[p]
                if i1 == n: continue
                q.append((pj1, i1))

    print(dp[-1] % mod)


    return


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

Submission status: Time Limit Exceeded

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

    print(dp[-1])


    return


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

Submission status: Time Limit Exceeded

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


    return


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

Submission status: Time Limit Exceeded

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


    return


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

Submission status: Time Limit Exceeded

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


    return


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