Problem:


Score : 100 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 21

a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

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

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

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

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

Sample Input 2

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

Sample Output 2

1

There is one way to make pairs, as follows:

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

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

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

Sample Output 4

102515160

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



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


Sample output:
3

Submission status: Accepted

Solution code:
def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

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

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

for S in range(1, 2**N):
    p = popcount(S)
    j = S & -S
    S2 = S
    for _ in range(p):
        if A[p-1][j.bit_length() - 1]:
            dp[S] = (dp[S - j] + dp[S])%mod
        S2 -= j
        j = S2 & -S2 
print(dp[-1])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

def itercomb(n,k):
    _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

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

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

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


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

Submission status: Accepted

Solution code:
range = xrange
input = raw_input
MOD = 10**9+7
 
n = int(input())

dp = [0] * (1 << n)
for i in [i for i, x in enumerate(input().split()) if x == '1']:
    dp[1 << i] = 1

npow = 1 << n

for i in range(n - 1):
    _dp = [0] * npow
    for j in [i for i, x in enumerate(input().split()) if x == '1']:
        jpow = 1 << j
        mask = 0
        while mask < npow:
            _dp[mask + jpow] += dp[mask]
            mask += 1 + ((mask+1) & jpow)
    for mask in range(npow):
        _dp[mask] %= MOD
    dp = _dp
 
print(sum(dp) % MOD)

Submission status: Accepted

Solution code:
def f(s, i):
    if i == n:
        return 1
    if memo[s] != -1:
        return memo[s]
    re = 0
    for j in range(n):
        if aij[i][j] and s & (1 << j):
            re += f(s - (1 << j), i + 1)
    re = memo[s] = re % md
    return re


md = 10 ** 9 + 7
n = int(input())
aij = [list(map(int, input().split())) for _ in range(n)]
memo = [-1] * (1 << n)
s = (1 << n) - 1
print(f(s, 0))

Submission status: Accepted

Solution code:
import itertools

MOD = 10**9 + 7


def main():
    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):
        pairs = []
        for j in range(N):
            if A[i][j] == 1:
                pairs.append(1 << j)
        for combi in itertools.combinations(range(N), r=i):
            x = 0
            for c in combi:
                x += 1 << c
            for p in pairs:
                if x & p == 0:
                    dp[i+1][x | p] = (dp[i+1][x | p] + dp[i][x]) % MOD

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
R = 1000000007

def dfs(x,y):
    if x == n:
        return 1
    if dp[y] > -1:
        return dp[y]
    sum = 0
    for j in range(n):
        b = 1 << j
        if a[x][j] == 1 and (y&b) == 0:
            sum += dfs(x+1, y|b)
            if sum > R:
                sum -= R
    dp[y] = sum
    return sum

n = inn()
a = [ 0 for i in range(n) ]
for i in range(n):
    a[i] = inl()
dp = [-1] * (2**n)
print(dfs(0,0))

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

dp[0] = 1

def dfs(state, c):
    if dp[state] != -1:
        return dp[state]
    ret = 0
    for i in range(n):
        if state & (1 << i) and a[c][i]:
            ret += dfs(state ^ (1 << i) , c + 1)
    dp[state] = ret % MOD
    return dp[state]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
mod=10**9+7
n=int(input())
A=[tuple(map(int,input().split())) for _ in range(n)]
DP=[-1]*(1<<n)
DP[0]=1

def dfs(s,m):
    if DP[s]!=-1:
        return DP[s]
    tmp=0
    for i in range(n):
        if (s>>i)&1 and A[m][i]:
            tmp+=dfs(s-(1<<i),m-1)
    DP[s]=tmp%mod
    return DP[s]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
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(s,m):
    if DP[s]!=-1:
        return DP[s]
    tmp=0
    for i in range(n):
        if (s>>i)&1==0 and A[m][i]==1:
            tmp+=dfs(s+(1<<i),m+1)
    DP[s]=tmp%mod
    return DP[s]

print(dfs(0,0))

Submission status: Accepted

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

#dp[i] : 集合iから始めたときの場合の数
dp = [-1] * (1 << n)
dp[(1 << n) - 1] = 1

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

Submission status: Accepted

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

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

memo = [-1] * (1 << n)
memo[0] = 1

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

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

Submission status: Accepted

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

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

memo = [-1] * (1 << n)
memo[(1 << n) - 1] = 1

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

print(dfs(0, 0))

Submission status: Accepted

Solution code:
P = 10 ** 9 + 7
N = int(input())
X = [input()[::2] for i in range(N)]
Y = [-1] * (1<<N)

def calc(x, n):
    if Y[x] >= 0:
        return Y[x]
    if n < 0:
        return 1
    
    ret = 0
    for j in range(N):
        if x & (1<<j) and X[n][j] == "1":
            ret += calc(x-(1<<j), n-1)
            ret %= P
    Y[x] = ret
    return ret

print(calc((1<<N)-1, N-1))

Submission status: Accepted

Solution code:


MOD = 1000000007

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

# dp[S] cant de match usando |S| primeros hombres y S mujeres
dp = [0] * (1 << n)
dp[0] = 1
for mask in range(1, 1 << n):
    i = bin(mask).count('1') - 1  # bin(6) => 0x110
    for j in range(n):
        if a[i][j] == 1 and mask & (1 << j):
            dp[mask] += dp[mask ^ (1 << j)]
            dp[mask] %= MOD
print(dp[(1 << n) - 1])

Submission status: Accepted

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

I = [ [ j for j in range(N) if Ai[j]] for Ai in A ]

memo = [-1]*(1<<N)
memo [0] = 1

def dfs(S,c ) :
    if memo[S] != -1:
        return memo[S]

    r = 0
    for i in I[c]: # bit count
        if S & (1<<i):
            r += dfs(S ^ (1<<i), c+1)
    memo[S] = r = r %MOD
    return r
print(dfs((1<<N)-1,0))

Submission status: Accepted

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

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

#bitDP
DPLIST=[-1]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=-1:
        return DPLIST[NOW]

    ANS=0

    for i in range(N):
        if A[x][i]==1 and NOW & (1<<i) ==0:
            ANS+=dp(NOW+(1<<i),x+1)

    ANS%=mod
    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [LI() for _ in range(n)]
    m = 2**n
    s = [[0] * m for _ in range(n+1)]
    s[0][0] = 1
    ii = [2**i for i in range(n)]
    for i in range(n):
        t = s[i+1]
        u = s[i]
        b = [ii[c] for c in range(n) if a[i][c]]
        for k in range(m):
            v = u[k]
            v = v % mod
            if v < 1:
                continue
            for j in b:
                if not (j & k):
                    t[k | j] += v

    return s[-1][-1] % mod


print(main())

Submission status: Accepted

Solution code:
n = int(input())
dp = [0] * (1 << n)
dp[0] = 1
curr = {0}
MOD = 10 ** 9 + 7
for i in range(n):
    compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
    nxt = set()
    for k in curr:
        p = dp[k] % MOD
        for c in compatibilities:
            if k & c:
                continue
            dp[k | c] += p
            nxt.add(k | c)
    curr = nxt
print(dp[(1 << n) - 1] % MOD)

Submission status: Accepted

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

I = [[j for j in range(N) if Ai[j]] for Ai in A]

memo = [-1]*(1 << N)
memo[0] = 1
def dfs(state, c):
    if memo[state] != -1:
        return memo[state]
    r = 0
    for i in I[c]:
        if state & (1 << i):
            r += dfs(state ^ (1 << i), c+1)
    memo[state] = r = r % MOD
    return r
print(dfs((1 << N)-1, 0))

Submission status: Accepted

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

cs = [0]*(1 << N)
used = [0]*(1 << N)
s = (1 << N) - 1
que = deque([(s, 0)])
cs[s] = 1
used[s] = 1

while que:
    state, c = que.popleft()
    v = cs[state] % MOD

    for i in range(N):
        if state & (1 << i) and A[c][i]:
            n_state = state ^ (1 << i)
            cs[n_state] += v
            if not used[n_state] and c+1 < N:
                que.append((n_state, c+1))
                used[n_state] = 1
print(cs[0] % MOD)

Submission status: Accepted

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

memo = [-1]*(1 << N)
memo[0] = 1
def dfs(state, c):
    if memo[state] != -1:
        return memo[state]
    r = 0
    for i in range(N):
        if state & (1 << i) and A[c][i]:
            r += dfs(state ^ (1 << i), c+1)
    memo[state] = r = r % MOD
    return r
print(dfs((1 << N)-1, 0))

Submission status: Accepted

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

ALL = 1 << N
S = [0]*ALL
MOD = 10**9 + 7
S[ALL-1] = 1
for k in range(N, 0, -1):
    I = [i for i in range(N) if A[k-1][i]]
    v = (1 << k) - 1
    while v < ALL:
        w = S[v] % MOD
        for i in I:
            if v & (1 << i):
                S[v ^ (1 << i)] += w
        x = v & -v; y = v + x
        v = ((v & ~y) // x >> 1) | y
print(S[0] % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N = int(input())
As = [int(input().replace(' ', ''), 2) for _ in range(N)]

patWsList = [[] for _ in range(N+1)]
for patW in range(2**N):
    num1 = sum([(patW >> i) & 1 for i in range(N)])
    patWsList[num1].append(patW)

dp = [0] * (2**N)
dp[-1] = 1
for iM, (A, patWs) in enumerate(zip(As, reversed(patWsList))):
    for patW in patWs:
        A2 = A & patW
        dpNow = dp[patW]
        for iW in range(N):
            if A2 & (1 << iW):
                dp[patW ^ (1 << iW)] += dpNow
                dp[patW ^ (1 << iW)] %= MOD

print(dp[0])

Submission status: Runtime Error

Solution code:
if __name__ == "__main__":
    n= int(input())
    h=[int(X) for X in input().split()]
    a=[int(x) for x in input().split()]
    dp = [0]*(n+1)
    x= 1<<(len(bin(n))-2)
    tree = [0]*(2*x)
    for i in range(n):
        p=h[i]+x
        an = 0
        while(p>1):
            if (p%2):
                an= max(tree[p-1],an)
            p=p//2
        dp[h[i]]=an+a[i]
        j= x+ h[i]
        while(j>0):
            tree[j]=max(dp[h[i]],tree[j])
            j=j//2

    print(max(dp))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

@njit('i8(i8,i4[:,:],i8[:,:],i8)', cache=True)
def solve(N, aff, dpt, MOD):
    for i, row in enumerate(aff):
        for idx, v in enumerate(row):
            if v == 1:
                dpt[i+1][(1<<idx):] += dpt[i][:-(1<<idx)]
        dpt[i+1] %= MOD
    return dpt[N][(1<<N)-1]

def main():
    MOD = 10**9 + 7
 
    N = int(input())
    aff = np.array([list(map(int, input().split())) for i in range(N)], dtype='int32')
    dpt = np.zeros((N+1, 1<<N), dtype='int64')
    dpt[0][0] = 1

    print(solve(N, aff, dpt, MOD))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
MOD = 10**9 + 7

def main():
 
    N = int(input())
    aff = np.array([list(map(int, input().split())) for i in range(N)], dtype='int32')
    dpt = np.zeros((N+1, 1<<N), dtype='int64')
    dpt[0][0] = 1

    print(solve(N, aff, dpt))

@njit(cache=True)
def solve(N, aff, dpt):
    for i, row in enumerate(aff):
        for idx, v in enumerate(row):
            if v == 1:
                dpt[i+1][(1<<idx):] += dpt[i][:-(1<<idx)]
        dpt[i+1] %= MOD
    return dpt[N][(1<<N)-1]

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
MOD = 10**9 + 7

def main():
 
    N = int(input())
    aff = np.array([list(map(int, input().split())) for i in range(N)], dtype='int32')
    dpt = np.zeros((N+1, 1<<N), dtype='int64')
    dpt[0][0] = 1

    print(solve(N, aff, dpt))

@njit('i8(i8,i4[:,:],i8[:,:])', cache=True)
def solve(N, aff, dpt):
    for i, row in enumerate(aff):
        for idx, v in enumerate(row):
            if v == 1:
                dpt[i+1][(1<<idx):] += dpt[i][:-(1<<idx)]
        dpt[i+1] %= MOD
    return dpt[N][(1<<N)-1]

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [[int(x) for x in input().split()] for i in range(n)]
dp = [-1 for i in range(1 << n)]
dp[0] = 1
def gethelp(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 += gethelp(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
print(gethelp(2**n-1, 0))

Submission status: Runtime Error

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

Submission status: Runtime Error

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 << n) - 1):
    i = bitcount(bit)
    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: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
from sys import stdin
input = lambda: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: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define forn(i,n) for(int i = 0; i< n;++i)
ll MOD = 1e9 + 7;
ll dp(int mask,int women_num,vector<vector<int>>& comp,int target,int n,vector<vector<int>>& save){
		if (save[mask][women_num] != -1){
			return save[mask][women_num];
		}
		if (mask == target){
			save[mask][women_num] = 1;
			return 1;
		}
		if(women_num == n){
			return 0;
		}
		ll ans = 0;
		for(int men =  0;men < n; ++men){
			if(((mask >> men) & 1 )== 0 && comp[men][women_num] == 1){
					ans += dp(mask | (1 << men), women_num+1,comp,target,n,save);
					ans %= MOD;
				}
			}
		save[mask][women_num] = ans%MOD;
		return ans%MOD;
	}

int main() {
	int n;
	cin >> n;
	vector<vector<int>> comp;
	vector<int> app;
	for(int men =0 ;men < n; ++men){
		for(int women = 0; women < n; ++women){
			int temp;
			cin >> temp;
			app.push_back(temp);
		 }
		 comp.push_back(app);
		 app.clear();
	 }
	 //cout << "done";
	vector<vector<int>> save(((1<<n) + 1),vector<int>(n+1,-1));
	int target = (1 << n) - 1; 
	cout << dp(0,0,comp,target,n,save)%MOD << endl;
}

Submission status: Runtime Error

Solution code:
n  =int(input())

comp = []
for i in  range(n):
    temp = []
    for j in range(n):
        a = input()
        temp.append(a)
    comp.append(temp)


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 comp[bit][women_num]:
            ans += make_pair(mask | 1 << bit,women_num+1)
            if ans >=MOD:
                ans -= MOD
    return ans

print(make_pair(0,0)%MOD)

Submission status: Runtime Error

Solution code:
lc = [0] * (1<<N)
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):
    lc[S] = lc[S>>1]+S%2
    for i in range(N):
        if S>>i&li[lc[S]-1][i] == 1:
            dp[S] = (dp[S]+dp[S-(1<<i)]) %mod
print(dp[(1<<N)-1])

Submission status: Runtime Error

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 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: Runtime Error

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
                dp[pj1] += dp[p]
                if i == n: continue
                q.append((pj1, i + 1))

    print(dp[-1] % mod)


    return


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

Submission status: Runtime Error

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 = [0 if j in z else 1 for j in range(N)]
        y = x[:]
        for j in z:
            if A[i][j]==1:
                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: Runtime Error

Solution code:
from itertools import combinations
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
from subprocess import*
with open('Main.cpp','w')as f:f.write(r"""
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y){return(x+=y)<mod?x:x-mod;}
int sub(int x,int y){return(x-=y)>= 0?x:x+mod;}
int dp[1<<21];
int n,a[21][21];
int main(){
  scanf("%d",&n);
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      scanf("%d",&a[i][j]);
    }
  }
  dp[0]=1;
  for(int b=1;b<(1<<n);++b){
    int bc=__builtin_popcount(b)-1;
    for(int i=0;i<n;++i){
      if((b>>i&1)&&a[bc][i]){
        dp[b]=add(dp[b],dp[b^(1<<i)]);
      }
    }
  }
  printf("%d\n",dp[(1<<n)-1]);
}
""")
call(('g++','Main.cpp'))
call(('./a'))

Submission status: Runtime Error

Solution code:
from numpy import*
def main():
  M=10**9+7
  a=loadtxt(open(0),'?',skiprows=1)
  n=len(a)
  dp=zeros(2**n,'i8')
  dp[0]=1
  for i in range(2**n-1):
    to=i|1<<arange(n)[a[bin(i).count('1')]]
    dp[to]+=dp[i]
    dp[to]%=M
  print(dp[-1])
main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

bit_to_i = {1<<i:i for i in range(N)}

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

for n in range(1,1<<N):
    bits = []
    m = n
    while n:
        x = n & (-n)
        bits.append(x)
        n -= x
    n = m
    k = len(bits)
    dp[n] = sum(dp[n-x] for x in bits if A[k-1][bit_to_i[x]]) % MOD

answer = dp[-1]
print(answer)