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:
def main():
    N=int(input())
    a=[]
    for i in range(N):
        a.append(list(map(int,input().split())))
    mod=10**9+7
    
    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=bin(i).count("1")
        for j in range(N):
            if i>>j&1==1 and a[m-1][j]==1:
                dp[i]+=dp[i-2**j]
        dp[i]%=mod
    
    print(dp[-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N=int(input())
    a=[]
    for i in range(N):
        A=list(map(int,input().split()))
        a.append(sum(2**i*A[i] for i in range(N)))
    mod=10**9+7
    
    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=bin(i).count("1")
        for j in range(N):
            if (i&a[m-1])>>j&1==1:
                dp[i]+=dp[i-2**j]
        dp[i]%=mod
    
    print(dp[-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
d=[0]*2**N
d[0]=1
s=set([0])
m=10**9+7
b=[2**i for i in range(N)]
for i in range(N):
    n=set()
    for j in range(N):
        if A[i][j]:
            y=b[j]
            for x in s:
                if x&y:continue
                d[x|y]=(d[x|y]+d[x])%m
                n.add(x|y)
    s=n
print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
d=[0]*2**N
d[0]=1
s=set([0])
m=10**9+7
b=[2**i for i in range(N)]
for i in range(N):
    n=set()
    for j in range(N):
        if A[i][j]:
            y=b[j]
            for x in s:
                if x&y==0:
                    d[x|y]=(d[x|y]+d[x])%m
                    n.add(x|y)
    s=n
print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
mod=10**9+7
input = sys.stdin.readline
N= int(input())
lst=[tuple(map(int,input().split())) for i in range(N)]
memo={}
memo[0]=1
def cost(a,n):
 if a in memo:
  return memo[a]
 else:
  ans=0
  for j in range(N):
   if ((a >> j) & 1) and lst[n-1][j]==1:
    if a&~(1<<j) in memo:
     ans+=memo[a&~(1<<j)]
    else:
     ans+=cost(a&~(1<<j),n-1)
  memo[a]=ans
  return ans
print(cost(2**N-1,N)%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = []
for _ in range(N):
    arr = np.array(list(map(int, input().split())))
    A.append(np.flatnonzero(arr))

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= 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)
dp[0] = 1

bitcount = [0]
for _ in range(n):
    bitcount += [i+1 for i in bitcount]

# 集めるDP
for bit in range(1,1 << n):
    i = bitcount[bit]
    for j in range(n):
        if ((bit >> j) & 1 == 1) and (a[i - 1][j] == 1):
            dp[bit] += dp[bit ^ (1 << j)]
    dp[bit] %= 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)
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] and ((bit >> j) & 1) ^ 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 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)
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] and ((bit >> j) & 1 ^ 1):
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 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)
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] and (bit >> j) & 1 ^ 1:
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 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)
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) & 1):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 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)
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] == 1) and ((bit >> j) & 1 == 0):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
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)]
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 ^ (1 << j)]
    dp[i] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
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 ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-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)
dp[0] = 1

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

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

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

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] * (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 ((bit >> j) & 1 == 0) and (a[i][j] == 1):
            dp[newbit] += dp[bit]
            dp[newbit] %= 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)
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 ((bit >> j) & 1 == 0) and (a[i][j] == 1):
            dp[newbit] += dp[bit]
            dp[newbit] %= 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)
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] == 1) and ((bit >> j) & 1 == 0):
            dp[newbit] += dp[bit]
            dp[newbit] %= 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)
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] == 1) and (bit != newbit):
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

def bfs(N,DPLIST,A,MOD):  # 幅優先探索
    frag = set([0])
    que = deque([0])
    while len(que) > 0:
        q = que.popleft()  # 次に立つbit数は?
        i = sum([i == '1' for i in bin(q)])
        for j in range(N):  # 移動先の候補
            bit = 1 << j
            newbit = q | bit
            if newbit == q:
                continue
            if newbit not in frag:  # 処理済みか否か
                que.append(newbit)
                frag.add(newbit)
            DPLIST[newbit] += DPLIST[q] * A[i][j]
            DPLIST[newbit] %= MOD
    return
bfs(n, dp, a, mod)
print(dp[-1])

Submission status: Time Limit Exceeded

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

for bit in bitlist:
    i = len(bit)
    j = sum(bitcal[k] for k in bit)
    for num in bit:
        dp[i][j] += dp[i - 1][j - 2 ** (n - num - 1)] * a[i - 1][num] % mod
    dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

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

for bit in bitlist:
    i = len(bit)
    j = sum(bitcal[k] for k in bit)
    for num in bit:
        dp[i][j] += dp[i - 1][j - 2 ** (n - num - 1)] * a[i - 1][num]
    dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

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

for i in range(n + 1):
    for j, bit in enumerate(product([0, 1], repeat=n)):
        if i == sum(bit):
            for num,k in enumerate(bit):
                if k == 1:
                    dp[i][j] += dp[i - 1][j - 2 ** (n - num - 1)] * a[i - 1][num]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(pow(2, n)):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 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] * (2 ** n)
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
for s in range(2 ** n):
    otoko = bin(s).count("1")
    i = otoko
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[2 ** n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [[0] * (2**N) for _ in range(N)]

q = [[] for _ in range(N)]
b = 1
for i in range(N):
    if a[0][i]:
        dp[0][b] = 1
        q[0].append(b)
    b <<= 1

for i in range(1,N):
    for k in q[i-1]:
        v = dp[i-1][k]
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                if dp[i][m] == 0: q[i].append(m)
                dp[i][m] = (dp[i][m] + v) % MOD
            b <<= 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [[0] * (2**N) for _ in range(N)]

q = [set() for _ in range(N)]
b = 1
for i in range(N):
    if a[0][i]:
        dp[0][b] = 1
        q[0].add(b)
    b <<= 1


for i in range(1,N):
    for k in q[i-1]:
        v = dp[i-1][k]
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                dp[i][m] = (dp[i][m] + v) % MOD
                q[i].add(m)
            b <<= 1

ans = dp[-1][2**N-1] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
N = NI()
a = [LI() for _ in range(N)]
dp = [{} for _ in range(N)]

b = 1
for i in range(N):
    if a[0][i]: dp[0][b] = 1
    b <<= 1

for i in range(1,N):
    for k,v in dp[i-1].items():
        b = 1
        for l in a[i]:
            if l and k & b == 0:
                m = k | b
                if m in dp[i]: dp[i][m] = (dp[i][m] + v) % MOD
                else: dp[i][m] = v
            b <<= 1
ans = sum(dp[-1].values()) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.buffer.readline().rstrip()
n = int(input())
dp = [None] * (1 << n)
dp[0] = 1
now = [0]
for _ in range(n):
    A = list(map(int, input().split()))
    next = []
    for i in range(n):
        if not A[i]:
            continue
        for U in now:
            if (U >> i) & 1:
                continue
            nU = U | 1 << i
            if dp[nU] is None:
                dp[nU] = dp[U]
                next.append(nU)
            else:
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    now = next

res = dp[-1]
if res is None:
    res = 0
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.buffer.readline().rstrip()
def resolve():
    n = int(input())

    dp = [None] * (1 << n)
    dp[0] = 1
    now = [0]
    for _ in range(n):
        A = list(map(int, input().split()))
        next = []
        for i in range(n):
            if not A[i]:
                continue
            for U in now:
                if (U >> i) & 1:
                    continue
                nU = U | 1 << i
                if dp[nU] is None:
                    dp[nU] = dp[U]
                    next.append(nU)
                else:
                    dp[nU] += dp[U]
                    if dp[nU] >= MOD:
                        dp[nU] -= MOD
        now = next

    res = dp[-1]
    if res is None:
        res = 0
    print(res)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())

    # dp[i][U] : 男 i 番目まで見た時、埋まっている女性の state が U の場合の数
    # i = U.popcount なので i を持つ必要はない
    dp = [None] * (1 << n)
    dp[0] = 1
    now = [0]
    for _ in range(n):
        A = list(map(int, input().split()))
        next = []
        for i in range(n):
            if not A[i]:
                continue
            for U in now:
                if (U >> i) & 1:
                    continue
                nU = U | 1 << i
                if dp[nU] is None:
                    dp[nU] = dp[U]
                    next.append(nU)
                else:
                    dp[nU] += dp[U]
                    if dp[nU] >= MOD:
                        dp[nU] -= MOD
        now = next

    res = dp[-1]
    if res is None:
        res = 0
    print(res)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n = int(input())

    # dp[i][U] : 男 i 番目まで見た時、埋まっている女性の state が U の場合の数
    dp = {0 : 1}
    for _ in range(n):
        A = list(map(int, input().split()))
        ndp = defaultdict(int)
        for i in range(n): # match させる女性
            if not A[i]:
                continue
            for U, val in dp.items():
                if (U >> i) & 1:
                    continue
                nU = U | 1 << i
                ndp[nU] += val
                if ndp[nU] >= MOD:
                    ndp[nU] -= MOD
        dp = ndp

    print(sum(dp.values()) % MOD)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())

    # dp[i][U] : 男 i 番目まで見た時、埋まっている女性の state が U の場合の数
    dp = [0] * (1 << n)
    dp[0] = 1
    for _ in range(n):
        A = list(map(int, input().split()))
        ndp = [0] * (1 << n)
        for i in range(n): # match させる女性
            if not A[i]:
                continue
            for U in range(1 << n):
                if (U >> i) & 1:
                    continue
                nU = U | 1 << i
                ndp[nU] += dp[U]
                if ndp[nU] >= MOD:
                    ndp[nU] -= MOD
        dp = ndp

    print(sum(dp) % MOD)
resolve()

Submission status: Time Limit Exceeded

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


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


dp = [[0]*(1 << N) for i in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for j in range(1, 1 << N):
    i = popcount(j)
    for k in range(N):
        if (j >> k) % 2 == 1:
            if a[i-1][k] == 1:
                dp[i][j] += dp[i-1][j ^ (1 << k)]
                dp[i][j] %= mod

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

Submission status: Time Limit Exceeded

Solution code:


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

    cand_s = [0]
    for i in range(1, n + 1):
        cand_i = set()
        for j in range(1, n + 1):
            if not a[i - 1][j - 1]:
                continue

            sj = 1 << (j - 1)
            for s in cand_s:
                if not s & sj:
                    dp[i][s | sj] += dp[i - 1][s]
                    dp[i][s | sj] %= modp
                    cand_i.add(s | sj)
        cand_s = list(cand_i)

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


submit()

Submission status: Time Limit Exceeded

Solution code:
n  =int(input())

comp = []
for i in  range(n):
    temp = [int(x) for x in input().split()]
    temp2= set()
    for j,e in enumerate(temp):
        if e == 1:
            temp2.add(j)
    comp.append(temp2)
MOD = 10**9+7
# 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
    if women_num == n:
        return 0
    ans = 0
    for bit in range(n):
        if ((mask >> bit) & 1 )== 0 and women_num in comp[bit]:
            ans += make_pair(mask | 1 << bit,women_num+1)
    return ans%MOD

print(make_pair(0,0)%MOD)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
# input = sys.stdin.readline

M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]

sys.setrecursionlimit(10**7)
dp = []
v = []
mask = 0
def count(msk,p):
    global dp,v,mask
    if msk == mask:return 1
    if p == n:return 0
    if (msk,p) in count.dp:return count.dp[(msk,p)]
    ans = 0
    for i in range(n):
        curr = (msk & (1<<i))
        if not curr and v[i][p]:
            ans = (ans + count(msk | 1<<i,p+1))%mod
    count.dp[(msk,p)] = ans
    return ans

n = val()



for i in range(n):v.append(li())


mask = (1<<n) - 1
dp = []
for i in range(mask+2):
    dp.append([-1]*(n + 2))
count.dp = {}
print(count(0,0))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline

M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]


dp = []
v = []
mask = 0
def count(msk,p):
    global dp,v,mask
    if msk == mask:return 1
    if p == n:return 0
    if (msk,p) in count.dp:return count.dp[(msk,p)]
    ans = 0
    for i in range(n):
        curr = (msk & (1<<i))
        if not curr and v[i][p]:
            ans = (ans + count(msk | 1<<i,p+1))%mod
    count.dp[(msk,p)] = ans
    return ans

n = val()



for i in range(n):v.append(li())


mask = (1<<n) - 1
dp = []
for i in range(mask+2):
    dp.append([-1]*(n + 2))
count.dp = {}
print(count(0,0))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline

M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]


dp = []
v = []
mask = 0
def count(msk,p):
    global dp,v,mask
    if msk == mask:return 1
    if p == n:return 0
    if (msk,p) in count.dp:return count.dp[(msk,p)]
    ans = 0
    for i in range(n):
        curr = (msk & (1<<i))
        if not curr and v[i][p]:
            ans = (ans + count(msk | 1<<i,p+1))%mod
    count.dp[(msk,p)] = ans
    return ans










n = val()



for i in range(n):v.append(li())


mask = (1<<n) - 1
dp = []
for i in range(mask+2):
    dp.append([-1]*(n + 2))
count.dp = {}
print(count(0,0))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline

M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]



n = val()

comp = []
for i in  range(n):
    temp = li()
    temp2 = set()
    for j,e in enumerate(temp):
        if e == 1:
            temp2.add(j)
    comp.append(temp2)

# n -> 21
target = (1 << n) -1
def make_pair(mask,women_num):
    if (mask,women_num) in make_pair.d:return make_pair.d[(mask,women_num)]
    if mask == target:
        return 1
    
    ans = 0
    for bit in range(n):
        if ((mask >> bit) & 1 )== 0 and women_num in comp[bit]:
            ans = (ans + make_pair(mask | 1 << bit,women_num+1))%mod
    make_pair.d[(make_pair,women_num)] = ans
    return ans
make_pair.d = {}
print(make_pair(0,0)%mod)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline

M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in input().rstrip()]



n = val()

comp = []
for i in  range(n):
    temp = li()
    temp2 = set()
    for j,e in enumerate(temp):
        if e == 1:
            temp2.add(j)
    comp.append(temp2)

# n -> 21
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 and women_num in comp[bit]:
            ans = (ans + make_pair(mask | 1 << bit,women_num+1))%mod
    return ans

print(make_pair(0,0)%mod)

Submission status: Time Limit Exceeded

Solution code:


n  =int(input())

comp = []
for i in  range(n):
    temp = [int(x) for x in input().split()]
    temp2= set()
    for j,e in enumerate(temp):
        if e == 1:
            temp2.add(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 and women_num in comp[bit]:
            ans += make_pair(mask | 1 << bit,women_num+1)
    return ans

MOD = 10**9+7
print(make_pair(0,0)%MOD)

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 = [None for s in range(1 << n)]
DP[0] = 1
def dp(s, l):
    if DP[s] != None:
        return DP[s]
    tmp = 0
    for i in range(n):
        if s & (1 << i) and A[l-1][i]:
            tmp += dp(~(1 << i) & s, l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1 << n)-1, n))