Problem:


Score : 100 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 21

a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

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

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

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

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

Sample Input 2

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

Sample Output 2

1

There is one way to make pairs, as follows:

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

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

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

Sample Output 4

102515160

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



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


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
p = 10 ** 9 + 7

b = [1 << i for i in range(n+1)]
nb = [~b_ for b_ in b]
DP = [0] * b[n]
DP[0] = 1

for S in range(1, b[n]):
    i = bin(S).count('1') - 1
    DP[S] = sum(DP[S & nb[j]] * A[i][j] for j in range(n)) % p

print(DP[b[n] - 1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [[int(i) for i in input().split()] for j in range(n)]
p = 10 ** 9 + 7

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

for S in range(1, 1 << n):
    i = bin(S).count('1') - 1
    DP[S] = sum(DP[S & ~(1 << j)] for j in range(n) if 1 << j and A[i][j]) % p

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

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

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = [ [int(j) for j in input().split()] for _ in range(N)]

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

for S in range(1<<N):
    i = bin(S).count("1")
    for j in range(N):
        if not (1<<j) & S and A[i-1][j] == 1: # vacant lot
            dp[i+1][S^(1<<j)] += dp[i][S] % MOD

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

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
A = [ [int(j) for j in input().split()] for _ in range(N)]

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

for S in range(1<<N):
    i = bin(S).count("1")
    for j in range(N):
        if not (1<<j) & S and A[i-1][j] == 1: # vacant lot
            dp[i+1][S^(1<<j)] += dp[i][S] % MOD

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

Submission status: Time Limit Exceeded

Solution code:


MOD = 1000000007

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

dp = [[0] * (1 << n) for _ in range(n + 1)]
for i in range(1 << n):
    dp[0][i] = 1
for i in range(1, n + 1):
    for mask in range(1, 1 << n):
        for j in range(n):
            if a[i - 1][j] == 1 and mask & (1 << j):
                dp[i][mask] += dp[i - 1][mask ^ (1 << j)]
                dp[i][mask] %= MOD
print(dp[n][(1 << n) - 1])

Submission status: Time Limit Exceeded

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+2**i,x+1)

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

print(dp(0,0)%mod)

Submission status: Time Limit Exceeded

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+2**i,x+1)

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0)%mod)

Submission status: Time Limit Exceeded

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

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

B=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if A[i][j]==1:
            B[i].append(j)
        
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 b in B[x]:
        if NOW & (1<<b)==0:
            ANS=(ANS+dp(NOW+2**b,x+1))%mod

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

Submission status: Time Limit Exceeded

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

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

B=[[] for i in range(N)]
for i in range(N):
    for j in range(N):
        if A[i][j]==1:
            B[i].append(j)
        
mod=10**9+7

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

def dp(NOW,x):

    if DPLIST[NOW]!=None:
        return DPLIST[NOW]

    ANS=0

    for b in B[x]:
        if NOW & (1<<b) ==0:
            ANS=(ANS+dp(NOW+2**b,x+1))%mod

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

Submission status: Time Limit Exceeded

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=[None]*(2**N)
DPLIST[2**N-1]=1

def dp(NOW,x):

    if DPLIST[NOW]!=None:
        return DPLIST[NOW]

    ANS=0

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

    DPLIST[NOW]=ANS
    return ANS

print(dp(0,0))

Submission status: Time Limit Exceeded

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)]
    s = collections.defaultdict(int)
    s[0] = 1
    ii = [2**i for i in range(n)]
    for i in range(n):
        t = collections.defaultdict(int)
        b = [ii[c] for c in range(n) if a[i][c]]
        for k,v in s.items():
            v = v % mod
            for j in b:
                if not (j & k):
                    t[k | j] += v
        s = t

    if len(s) == 0:
        return 0

    return list(s.values())[0] % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
dp = {0: 1}
MOD = 10 ** 9 + 7
for i in range(n):
    compatibilities = [1 << i for i, v in enumerate(input().split()) if v == '1']
    ndp = defaultdict(lambda: 0)
    for k, p in dp.items():
        for c in compatibilities:
            if k & c:
                continue
            ndp[k | c] += p
            ndp[k | c] %= MOD
    dp = ndp
    # print(i, len(dp))
print(sum(dp.values()) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
src = [int(input().replace(' ',''), 2) for i in range(N)]

MOD = 10**9+7
dp = [None] * (2**N)
dp[0] = 1

def rec(b):
    if dp[b] is not None: return dp[b]
    i = bin(b).count('1') - 1
    ret = 0
    for j in range(N):
        if (b & src[i] & (1<<j)) == 0: continue
        ret += rec(b^(1<<j))
    ret %= MOD
    dp[b] = ret
    return ret

print(rec(2**N - 1))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
table=[set() for i in range(N)]
for i in range(N):
    A=[int(i) for i in input().split()]
    for j in range(N):
        if A[j]==1:
            table[i].add(j)
mod=10**9+7
dp=[[0]*(1<<N) for i in range(N+1)]
dp[0][0]=1
for S in range(1<<N):
    i=bin(S).count('1')
    for j in table[i-1]:
        if S&(1<<j)==0:
            dp[i+1][S | (1<<j)]+=dp[i][S]
            dp[i+1][S | (1 << j)]%=mod
print(dp[N][(1<<N)-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
table=[set() for i in range(N)]
for i in range(N):
    A=[int(i) for i in input().split()]
    for j in range(N):
        if A[j]==1:
            table[i].add(j)
mod=10**9+7
dp=[0]*(1<<N)
dp[0]=1
H=set()
H.add(0)
for i in range(N):
    nH=set()
    for S in H:
        for j in table[i]:
            if S&(1<<j)==0:
                dp[S|(1<<j)]+=dp[S]
                dp[S | (1 << j)]%=mod
                nH.add(S|(1<<j))

    H=nH

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N=int(input())
table=[set() for i in range(N)]
for i in range(N):
    A=[int(i) for i in input().split()]
    for j in range(N):
        if A[j]==1:
            table[i].add(j)
mod=10**9+7
dd=defaultdict(int)
dd[0]=1
for i in range(N):
    ndd=defaultdict(int)
    for S,n in dd.items():
        for j in table[i]:
            if S&(1<<j)==0:
                ndd[S|(1<<j)]+=n
                ndd[S | (1 << j)]%=mod
    #print(ndd)
    dd=ndd
a=0
for i in range(N):
    a+=1<<i
print(dd[a]%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
mod=10**9+7
dd=defaultdict(int)
dd[0]=1
for i in range(N):
    ndd=defaultdict(int)
    for S,n in dd.items():
        for j in range(N):
            if A[i][j]==1 and S&(1<<j)==0:
                ndd[S|(1<<j)]+=n
                ndd[S | (1 << j)]%=mod
    #print(ndd)
    dd=ndd
a=0
for i in range(N):
    a+=1<<i
print(dd[a]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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):
 for j,s in enumerate(bin(A[bin(I).count('1')]&~I)[:1:-1]):
  if s=='1':p[I|1<<j]+=p[I];p[I|1<<j]%=10**9+7
print(p[-1])

Submission status: Time Limit Exceeded

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&2**j:p[I+2**j]+=p[I];p[I+2**j]%=10**9+7
print(p[-1])

Submission status: Time Limit Exceeded

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):
  x=1<<j;
  if a&x:dp[I|x]+=dp[I];dp[I|x]%=10**9+7
print(dp[-1])

Submission status: Time Limit Exceeded

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):
  x=1<<j;
  if a&x:dp[I+x]+=dp[I];dp[I+x]%=10**9+7
print(dp[-1])

Submission status: Time Limit Exceeded

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]
        mask = 1 << (N-1)
        for iW in range(N):
            if A2 & mask:
                 dp[patW ^ mask] += dpNow
                 dp[patW ^ mask] %= MOD
            mask >>= 1

print(dp[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**9 + 7
a = [list(map(int,input().split())) for _ in range(n)]
b = [[] for i in range(n)] 
for i in range(n):
  for j in range(n):
    if a[i][j]:
      b[i].append(j)
dp = [0] * 2**n
dp[0] = 1
for j in range(n):
  for i in range(2**n-1,-1,-1):
    if dp[i]:
      for k in b[j]:
        if i & 2**k:
          continue
        dp[i|2**k] += dp[i]
        dp[i|2**k] %= mod
print(dp[-1]%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
  MOD = 1000000007
  n = int(input())
  match = [list(map(int, input().split())) for _ in range(n)]
  
  dic = {}
  def dp(stat, index):
    if index == n:return 1
    if stat in dic:
      return dic[stat]
  
    ret = 0
    mask = 1
    match_index = match[index]
    for i in range(n):
      if mask & stat or not match_index[i]:
        mask <<= 1
        continue
      ret += dp(stat | mask, index + 1)
      mask <<= 1
    ret %= MOD
    dic[stat] = ret
    return ret
  
  print(dp(0, 0))
  
main()

Submission status: Time Limit Exceeded

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

dic = {}
def dp(stat, index):
  if index == n:return 1
  if stat in dic:
    return dic[stat]

  ret = 0
  mask = 1
  for i in range(n):
    if mask & stat:
      mask <<= 1
      continue
    if not match[index][i]:
      mask <<= 1
      continue
    ret += dp(stat | mask, index + 1)
    mask <<= 1
  ret %= MOD
  dic[stat] = ret
  return ret

print(dp(0, 0))

Submission status: Accepted

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


print(dp[-1]%mod)

Submission status: Accepted

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

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

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]

for i in range((1 << N) - 1):
    c = bit_count[i]
    if DP[i] == 0:
        continue
    for j in range(N):
        if (Match[c] >> j) & 1 == 1:
            if (i >> j) & 1 == 0:
                DP[i| (1 << j)] += DP[i]
                DP[i| (1 << j)] %= mod
print(DP[-1] % mod)

Submission status: Accepted

Solution code:
def edu_dp_d_matching():
    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))
    dp = [[0] * (1 << n) for _ in range(n)]
    for i in range(n):
        if a[0][i] == 1: dp[0][(1 << i)] = 1
    for i in range(1, n):
        for k in range(1 << n):
            if dp[i - 1][k] == 0: continue
            for j in range(n):
                if a[i][j] == 0 or k & (1 << j) != 0: continue
                dp[i][k | (1 << j)] += dp[i - 1][k]

    print(dp[-1][-1] % (pow(10, 9) + 7))


edu_dp_d_matching()

Submission status: Accepted

Solution code:
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 i in range(1,2**n):
    x=bin(i)[2:]
    y=x.count('1')
    for j in range(len(x)):
      if x[-j-1]=='1':
        if a[y-1][j]==1:
            dp[i]+=dp[i-(2**j)]
            dp[i]%=mod


print(dp[-1])

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) #xorでibit目の1を0に
    memo[state] = r = r % MOD
    return r
print(dfs((1 << N)-1, 0))
#c 何人目の男性か(女性が何人すでにマッチングしてるか)
#マッチングしてない(1)

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

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

print(dp[-1])

Submission status: Accepted

Solution code:
MOD = 1000000007

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

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

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

print(dp[-1])

Submission status: Accepted

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

def b(n,k):
    return (n>>k)&1
MOD=10**9+7

dp=[[0 for j in range(1<<n)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for S in range(1<<n):
        if (dp[i][S]):
            for j in range(n):
                if (b(S,j)==0 and a[i][j]==1):
                    dp[i+1][S^(1<<j)]+=(dp[i][S^(1<<j)]+dp[i][S])%MOD
                    dp[i+1][S^(1<<j)]%=MOD
print(dp[n][-1])

Submission status: Accepted

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
DP=[-1]*(1<<N)
def f(x,k):
  if x==0:
    DP[x]=1
  if DP[x]!=-1:
    return DP[x]
  DP[x]=0
  for i in range(N):
    if x&(1<<i):
      if A[k][i]:
        DP[x]+=f(x^(1<<i),k+1)
  return DP[x]

print(f((1<<N)-1,0)%(10**9+7))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[0]*2**n
mod=10**9+7
dp[0]=1
for i in range(2**n-1):
    cnt=-1
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
    for j in range(n):
        if (i>>j)&1==0:
            if a[cnt+1][j]:
                dp[i|pow(2,j)]+=dp[i]
                dp[i|pow(2,j)]%=mod
print(dp[2**n-1])

Submission status: Accepted

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

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

ra = range
enu = enumerate


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


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


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


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


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

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

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

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

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

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

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

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

from numba import njit


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


@njit('i8(i8)', cache=True)
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 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


@njit('(i8,i8[:,:])', cache=True)
def solve(N, A):  # 遷移のi==|s|の遷移しか生じないことに注目すれば
    dp = np.zeros((N + 1, 1 << N), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        for s in range(1 << N):
            if popcount(s) != i:  # 自分的にはこっちの枝刈りのほうがしっくり
                continue
            # if dp[i, s] == 0:  # 遷移するものがない
            #     continue
            for j in range(N):
                if (s >> j) & 1 == 0 and A[i, j] == 1:
                    dp[i + 1, s + (1 << j)] += dp[i, s]
                    dp[i + 1, s + (1 << j)] %= MOD
    print(dp[N, (1 << N) - 1] % MOD)


@njit('(i8,i8[:,:])', cache=True)
def solve2(N, A):  # iの代わりにsから情報を得る #s1 \subset s2 ならばs1<s2が成り立つので小さい方からforすればdpが成り立つ
    dp = np.zeros((1 << N), dtype=np.int64)
    dp[0] = 1
    for s in range(1 << N):
        for j in range(N):
            if (s >> j) & 1 == 0 and A[popcount(s), j] == 1:
                dp[s + (1 << j)] += dp[s]
                dp[s + (1 << j)] %= MOD
    print(dp[(1 << N) - 1] % MOD)


# solve2(N, A)
solve(N, A)

Submission status: Accepted

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

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

ra = range
enu = enumerate


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


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


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


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


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

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

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

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

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

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

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

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

from numba import njit


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


@njit('(i8,i8[:,:])', cache=True)
def solve(N, A):  # 遷移のi==|s|の遷移しか生じないことに注目すれば
    dp = np.zeros((N + 1, 1 << N), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        for s in range(1 << N):
            if dp[i, s] == 0:  # 遷移するものがない
                continue
            for j in range(N):
                if (s >> j) & 1 == 0 and A[i, j] == 1:
                    dp[i + 1, s + (1 << j)] += dp[i, s]
                    dp[i + 1, s + (1 << j)] %= MOD
    print(dp[N, (1 << N) - 1] % MOD)


@njit('i8(i8)', cache=True)
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 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


@njit('(i8,i8[:,:])', cache=True)
def solve2(N, A):  # iの代わりにsから情報を得る #s1 \subset s2 ならばs1<s2が成り立つので小さい方からforすればdpが成り立つ
    dp = np.zeros((1 << N), dtype=np.int64)
    dp[0] = 1
    for s in range(1 << N):
        for j in range(N):
            if (s >> j) & 1 == 0 and A[popcount(s), j] == 1:
                dp[s + (1 << j)] += dp[s]
                dp[s + (1 << j)] %= MOD
    print(dp[(1 << N) - 1] % MOD)


solve2(N, A)
# solve(N, A)

Submission status: Accepted

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

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

ra = range
enu = enumerate


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


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


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


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


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

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

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

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

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

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

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

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

from numba import njit


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


@njit('(i8,i8[:,:])', cache=True)
def solve(N, A):  # 遷移のi==|s|の遷移しか生じないことに注目すれば
    dp = np.zeros((N + 1, 1 << N), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        for s in range(1 << N):
            if dp[i, s] == 0:  # 遷移するものがない
                continue
            for j in range(N):
                if (s >> j) & 1 == 0 and A[i, j] == 1:
                    dp[i + 1, s + (1 << j)] += dp[i, s]
                    dp[i + 1, s + (1 << j)] %= MOD
    print(dp[N, (1 << N) - 1] % MOD)


solve(N, A)

Submission status: Accepted

Solution code:

def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



N=10**9 + 7
n=int(input())
ar = [list(map(int,input().split())) for _ in range(n)]   
total=1<<n
bits=[[]for _ in range(n+1)]
dp=[[0]*(total+5) for j in range(n+5)]

for i in range(n):
    if ar[0][i]==1:
        dp[0][1<<(n-1-i)]=1

for j in range(total):
    i=countSetBits(j)-1
    for k in range(0,n):
        if ar[i][n-k-1]==1 and j&(1<<k):
            dp[i][j]=(dp[i][j]+dp[i-1][j&(~(1<<k))])%N

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

def permanent(A):
    # O(N2^N) algorithm
    N = A.shape[0]

    # 残す列の集合 -> 行の和の積
    products = np.ones(1 << N, np.int64)
    for r in range(N):
        # r行目の計算をする
        row_sum = np.zeros(1 << N, np.int64)
        for n in range(N):
            row_sum[1 << n:1 << n + 1] = row_sum[:1 << n] + A[r, n]
        products *= row_sum
        products %= MOD

    # 符号をかけて集計する
    sgn = np.ones(1 << N, np.int64)
    for n in range(N):
        sgn[1 << n:1 << n + 1] = -sgn[:1 << n]

    products = products * sgn[::-1]

    perm = products.sum() % MOD
    return perm

N = int(readline())
A = np.array(read().split(), np.int64).reshape(N, N)

print(permanent(A))

Submission status: Accepted

Solution code:
import numpy as np

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

    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

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

if __name__ == '__main__':
    main()