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:
import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7

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

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

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)
lst = [0]

for i in range(N):
    tmp = []
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理        
        for k in lst:
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
                tmp.append(k + (1 << j))
    
        # print (dp[i + 1])
        # print (lst)
    lst = tmp

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

Submission status: Time Limit Exceeded

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

# import time
# s = time.time()

MOD = 10 ** 9 + 7

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

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

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)

for i in range(N):
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理
        for k in range(1 << N):
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
        # print (dp[i + 1])

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

# f = time.time()

# print (f - s, '秒')

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

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

dp[0][0] = 1
# for tmp in dp:
#     print (tmp)

for i in range(N):
    for j in range(N):
        if A[i][j] == 0: #仲良くない時
            continue
        #以下仲が良い時のみの処理
        for k in range(1 << N):
            if (1 << j) & k == 0: #まだペアになっていない女の人の時
                dp[i + 1][k + (1 << j)] = (dp[i + 1][k + (1 << j)] + dp[i][k]) % MOD
        # print (dp[i + 1])

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

Submission status: Time Limit Exceeded

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

Solution code:
def main():
    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]*(1<<n)
    dp[0]=1
    for s in range(1<<n):
        i=format(s,'b').count('1')
        for j in range(n):
            if (s>>j)&1 and A[i-1][j]==1:
              dp[s]+=dp[s^(1<<j)]
              dp[s]%=mod   
              
    print(dp[-1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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]*(1<<n) for _ in range(n+1)]
    dp[0][0]=1
    for i in range(1,n+1):
        for s in range(0,1<<n):
            for j in range(n):
                if (s>>j)&1 and A[i-1][j]==1:
                    dp[i][s]+=dp[i-1][s^(1<<j)]
                    dp[i][s]%=mod
                    
    print(dp[n][(1<<n)-1])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    N=int(input())
    A=[list(map(int,input().split())) for i in range(N)]

    mod=10**9+7
    qqq=2**N

    data=[[] for i in range(2**N)]
    que=[0]

    dp=[0]*qqq
    dp[0]=1

    flag=[0]*qqq
    flag[0]=1

    que=[0]
    i=0

    while que:
        H=[]
        h=[0]*qqq
        for u in que:
            if u==qqq-1:
                break
            for j in range(N):
                if u&(1<<j)==0 and A[i][j]==1:
                    num=u+(1<<j)
                    h[num]=(h[num]+dp[u])%mod
                    if flag[num]==0:
                        flag[num]=1
                        H.append(num)
        else:  
            dp=h
            que=H
            i+=1
            continue
        break
    print(dp[-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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


def bit(n, k):  # nのkbit目を返す
    return (n >> k) & 1


def bit_count(n):
    return bin(n).count("1")


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

for s in range(1, 1 << N):
    i = bin(s).count("1")  # i人目の男とのマッチング
    for j in range(N):
        if (s >> j) & 1 and A[i-1][j]:
            dp[s] = (dp[s] + dp[s ^ (1 << j)]) % mod

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

Submission status: Time Limit Exceeded

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


def bit(n, k):  # nのkbit目を返す
    return (n >> k) & 1


def bit_count(n):
    return bin(n).count("1")


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

for s in range(1, 1 << N):
    i = bit_count(s)  # i人目の男とのマッチング
    for j in range(N):
        if bit(s, j) and A[i-1][j]:
            dp[s] = (dp[s] + dp[s ^ (1 << j)]) % mod

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

mod = 10**9+7

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
DP = defaultdict(int)
DP[0] = 1
for i in range(n):
    nxt = defaultdict(int)
    for key, value in DP.items():
        for j in range(n):
            mask = 1<<j
            if key & mask == 0 and a[i][j]:
                nxt[key|mask] += value
                nxt[key|mask] %= mod
    DP = nxt
state = (1<<n) - 1
ans = DP[state]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import *
n=int(input())
A=[list(map(int,input().split()))for _ in range(n)]
mod=10**9+7
p=[2**i for i in range(n)]
dp=[0]*2**n
dp[0]=1
for i,a in enumerate(A):
    for q in combinations(p,i+1):
        dp[sum(q)]=sum([dp[sum(q)&~p[j]]*a[j]for j in range(n)])%mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
# この方法だと、
# 参加している女性の数を数える部分 : c = bin(state).count('1')
# 一人減らして場合の数を足す部分 : for i in range(N): ...
# で、それぞれO(N)なので、
# 全体として 2 * N * 2**N 回の計算が必要
# 最大で N = 21 のときは間に合わない

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


for state in range(1, 2**N):
  c = bin(state).count('1')
  for i in range(N):
    if state & (1<<i):
      dp[state] += dp[state ^ (1<<i)]*A[c-1][i]
      dp[state] %= MOD

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

Submission status: Time Limit Exceeded

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

Solution code:
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])

Submission status: Time Limit Exceeded

Solution code:
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 j in pair_dic[i]:
#         for k in range(n):
for i in range(n):
    for k in range(n):
        for j in pair_dic[i]:
            if( (a[i][k] == 1) & ( ((j&(1<<k)) >>k == 0 ) )):
                dp[j + (1<<k)] += dp[j]
                dp[j + (1<<k)] = dp[j + (1<<k)] % MOD


print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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 j in pair_dic[i]:
        for k in range(n):
            if( (a[i][k] == 1) & ( ((j&(1<<k)) >>k == 0 ) )):
                dp[j + (1<<k)] += dp[j]
                dp[j + (1<<k)] = dp[j + (1<<k)] % MOD


print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def popcnt(x):
    res = 0
    while x:
        x &= x - 1
        res += 1
    return res


def matching(n, m):
    mod = 10**9 + 7
    maxmask = 1 << n
    d = [0] * maxmask
    d[0] = 1
    for mask in range(1, maxmask):
        x = popcnt(mask) - 1
        has_bits = mask
        while has_bits:
            has_bits_without_lowest_bit = has_bits & (has_bits - 1)
            current_bit = has_bits ^ has_bits_without_lowest_bit
            has_bits = has_bits_without_lowest_bit
            mask_without_bit = mask ^ current_bit
            y = popcnt(current_bit - 1)
            if m[x][y]:
                d[mask] = (d[mask] + d[mask_without_bit]) % mod
    return d[-1]

def main():
    n = int(input())
    m = [None] * n
    for i in range(n):
        m[i] = [int(x) for x in input().split()]
    return matching(n, m)


print(main())

Submission status: Time Limit Exceeded

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, x in enumerate(xs):
    for ai in x:
        for x in itercomb(N, i):
            if (not x&ai):
                d[x|ai] = (d[x|ai]+d[x])%M
print(d[-1])

Submission status: Time Limit Exceeded

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(sum(int(x)*(1<<i) for i, x in enumerate(input().split())))
M=10**9+7
d = [0]*(1<<N)
d[0] = 1
for i in range(N):
    a = xs[i]
    for j in combinations(ss, i):
        x = sum(j)
        for k in range(N):
            ai = ((a//(1<<k))%2)<<k
            if ai and (not x&ai):
                d[x|ai] = (d[x|ai]+d[x])%M
print(d[-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)]

nn = 1 << n

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

for bit in range(nn):
    cur = dp[bit] % mod
    if cur == 0:
        continue
    i = bin(bit).count("1")
    for j in range(n):
        bit_new = bit | (1 << j)
        if bit_new != bit and a[i-1][j] == 1:
            dp[bit_new] += cur

print(dp[-1] % mod)

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 = [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):
        bit_new = bit | (1 << j)
        if bit_new != bit and a[i-1][j] == 1:
            dp[bit_new] += dp[bit]
            dp[bit_new] %= mod

print(dp[-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 = [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)]
    dp[bit] %= mod

print(dp[2**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 = [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)]
            dp[bit] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n):
    a = [int(x) for x in input().split()]
    for j in range(n):
        for bit in range(1 << n):
            if a[j] == 1 and (bit & 1 << j):
                dp[i+1][bit] += dp[i][bit ^ (1 << j)]

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

Submission status: Time Limit Exceeded

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

for s in range(1, 2**N):
    i = bin(s).count("1")
    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: Time Limit Exceeded

Solution code:
MOD = 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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations,product
p = 10**9+7
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
dp = {x:[0 for _ in range(N)] for x in product((0,1),repeat=N)}
for z in combinations(range(N),1):
    for j in z:
        if A[N-1][j]==1:
            x = tuple([0 if j in z else 1 for j in range(N)])
            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 A[i][j]==1:
                x = [0 if j in z else 1 for j in range(N)]
                y = x[:]
                y[j] = 1
                x = tuple(x)
                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: Time Limit Exceeded

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),i):
        x = tuple([1 if i in z else 0 for i in range(N)])
        for j in G[i]:
            if x[j]==0:
                y = list(x[:])
                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: Time Limit Exceeded

Solution code:
from itertools import 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)
dp = {x:[0 for _ in range(N)] for x in product((0,1),repeat=N)}
for x in product((0,1),repeat=N):
    if sum(x)==N-1:
        for j in G[N-1]:
            if x[j]==0:
                dp[x][N-1] = 1
for i in range(N-2,-1,-1):
    for x in product((0,1),repeat=N):
        if sum(x)==i:
            for j in G[i]:
                if x[j]==0:
                    y = list(x[:])
                    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: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**9+7
c = []
for i in range(n):
	a = [int(x) for x in input().strip().split()]
	c.append(a)

dp = [[None for i in range(1<<n)] for j in range(n)]
def solve(i,b):
	if dp[i][b]:
		return dp[i][b]
	if i==n-1:
		for j in range(n):
			if b & (1<<j)==0 and c[i][j]==1:
				dp[i][b] = 1
				return 1
	
	dp[i][b] = 0			
	for j in range(n):
		if b & (1<<j)==0 and c[i][j]==1:
			dp[i][b]+=solve(i+1,b|(1<<j))%mod
	return dp[i][b]
	
print(solve(0,0))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
n = int(input())
can = []
for i in range(n):
    row = list(map(int, input().split()))
    can.append(row)
dp = [0] * (1 << n)
dp[0] = 1
for mask in range((1 << n) - 1):
    a = bin(mask).count('1')
    for b in range(n):
        if can[a][b] and not (mask & (1 << b)):
            mask2 = mask ^ (1 << b)
            dp[mask2] = (dp[mask2] + dp[mask]) % MOD
print(dp[(1 << n) - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [list(map(int, sys.stdin.readline().split())) for _ in range(rows_number)]

def main():
    md=10**9+7
    n=int(input())
    aa=LLI(n)
    lov=[[] for _ in range(n)]
    for i,ar in enumerate(aa):
        for j,a in enumerate(ar):
            if a:lov[i].append(j)
    dp=[0]*(1<<n)
    dp[0]=1
    for s in range((1<<n)-1):
        pre=dp[s]
        if pre==0:continue
        i=bin(s).count("1")
        for j in lov[i]:
            if s>>j&1:continue
            ns=s|1<<j
            dp[ns]=(dp[ns]+pre)%md
    print(dp[-1])
    #print(dp)

main()

Submission status: Time Limit Exceeded

Solution code:
def solve(man, matched):
#     print(man, matched)
    if man == N:
        return 1
    res = 0
    for idx, i in enumerate(arr[man]):
        if i == "1" and idx not in matched:
            matched.append(idx)
            res += solve(man+1, matched) % MOD
            matched.remove(idx)
    return res

MOD = 1e9 + 7 
N = int(input())
arr = []
for i in range(N):
    arr.append(input().split())
matched = []
print(int(solve(0, matched)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n = int(input())
    e = 1 << n
    to_love = []
    for _ in range(n):
        aa = list(map(int, input().split()))
        s = 0
        for i, a in enumerate(aa):
            if a: s += 1 << i
        to_love.append(s)
    # print(to_love)
    dp = [0] * e
    dp[e - 1] = 1
    for i in range(n):
        for j in range(e):
            pre = dp[j]
            if pre == 0: continue
            partners = to_love[i] & j
            for p in range(n):
                if partners & 1:
                    bitp = 1 << p
                    dp[j - bitp] = (dp[j - bitp] + pre) % md
                partners >>= 1
        # print(dp)
    print(dp[0])

main()

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())


def new_matrix(in_matrix,xi,yi):
    out_matrix = [ [ w for j, w in enumerate(v) if j != xi ]  for i, v in enumerate(in_matrix) if i != yi ]
    return out_matrix

def div_gov(in_matrix,n):
    if n == 1:
        return in_matrix[0][0]
    else:
        return sum( [ div_gov(new_matrix(in_matrix,i,0),n-1) for i in range(n) if in_matrix[0][i] == 1 ] ) % mod 



board = [ [ int(v) for v in input().split() ] for i in range(n)] 
print(div_gov(board,n))

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
n = int(input())


def new_matrix(in_matrix,xi,yi):
    out_matrix = [ [ w for j, w in enumerate(v) if j != xi ]  for i, v in enumerate(in_matrix) if i != yi ]
    return out_matrix

def div_gov(in_matrix,n):
    if n == 1:
        return in_matrix[0][0]
    else:
        return sum( [ in_matrix[0][i] * div_gov(new_matrix(in_matrix,i,0),n-1) for i in range(n) ] ) % mod 



board = [ [ int(v) for v in input().split() ] for i in range(n)] 
print(div_gov(board,n))

Submission status: Time Limit Exceeded

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

def main():
  N = int(input())
  A = [tuple(map(int,input().split())) for _ in range(N)]
  MOD =10**9+7

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

  for i in range(N):
    nextdp = [0 for _ in range(1<<N)]
    for j in range(1<<N):
      if dp[j] != 0:
        for k in range(N):
          if (j>>k)&1 == 0 and A[i][k] == 1:
            idx = j|(1<<k)
            nextdp[idx] += dp[j]
            nextdp[idx] %= MOD
    dp = nextdp

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 for _ in range(1<<N)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
  for j in range(1<<N):
    if dp[i][j] != 0:
      for k in range(N):
        if (j>>k)&1 == 0 and A[i][k] == 1:
          dp[i+1][j|(1<<k)] += dp[i][j]
          dp[i+1][j|(1<<k)] %= MOD
print(dp[N][(1<<N)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
graph = dict()
for i in range(n):
    _input = [int(i) for i in sys.stdin.readline().split()]
    graph[i] = [d for d, content in enumerate(_input) if content == 1]
memo_ls = [0 for i in range(2**n)]
# memo_ls[i] : 状態がiの時に有りうるペアの数
memo_ls[0] = 1
for i in range(1, 1 << n):
    j = bin(i).count("1")-1
    for ind in graph[j]:
        if not (i >> ind) & 1:
            continue
        _from = i - (1<<ind)
        if _from < 0:
            continue
        memo_ls[i] += memo_ls[_from]
        memo_ls[i] %= 10**9 + 7
print(memo_ls[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
graph = dict()
for i in range(n):
    _input = [int(i) for i in sys.stdin.readline().split()]
    graph[i] = _input
memo_ls = [0 for i in range(2**n)]
# memo_ls[i] : 状態がiの時に有りうるペアの数
memo_ls[0] = 1
for i in range(1, 1 << n):
    j = bin(i).count("1")-1
    for ind, k in enumerate(graph[j]):
        if k == 0:
            continue
        if not (i >> ind) & 1:
            continue
        _from = i - (1<<ind)
        if _from < 0:
            continue
        memo_ls[i] += memo_ls[_from]
        memo_ls[i] %= 10**9 + 7
print(memo_ls[-1])

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
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 i == str(bin(bit)).count("1") :
            for j in range(N) :
                if not (bit & (1 << j)) :
                    if A[i][j] == 1 :
                        dp[i+1][bit | (1 << j)] += dp[i][bit]

ans = dp[N][(1 << N) - 1] % (MOD)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

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

dp = {}
for i in range(n, -1, -1):
  for s in combinations(range(n), i):
    dp[s] = 0
dp[tuple(range(n))] = 1

for i in range(n, 0, -1):
  for s in combinations(range(n), i):
    t = set(s)
    v = dp[s]
    for j in s:
      if a[n - i][j] == 1:
        dp[tuple(sorted(t - set([j])))] += v

print(dp[tuple([])] % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

MOD = 10 ** 9 + 7
N=int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

dp = np.zeros(1<<N, dtype=np.uint32)
dp[0] = 1

for A_row in A:
    prev = dp.copy()
    dp = np.zeros_like(prev)
    for n,a in enumerate(A_row):
        if not a:
            continue
        x = 1 << n
        dp[x:] += prev[:-x]
        dp[dp>MOD] -= MOD

answer = dp[-1]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
INF = float('inf')
mod = 10**9+7

popcount = lambda s: bin(s).count('1')
N = int(input())
a = [[int(x) for x in input().split()] for i in range(N)]
dp = [0] * (1<<N)
dp[0] = 1
for s in range(1<<N):
    i = popcount(s)
    for j in range(N):
        if (s>>j)&1 and a[i-1][j]:
            dp[s] += dp[s^(1<<j)]
            dp[s] %= mod
print(dp[(1<<N)-1])