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:
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: Accepted

Solution code:
import numpy as np

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

Submission status: Accepted

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

dp=[0 for _ in range(1<<N)]
dp[0]=1
# 1<<N=2**N
for S in range(1,1<<N):
    i=bin(S).count('1')
    for x in range(N):
        if (S>>x & 1) and a[i-1][x]==1:
            dp[S]=(dp[S]+dp[S^(1<<x)])%MOD

print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = ILL(N)


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

dp[0] = 1

for b in range(1,1<<N):
  i = count_bit(b)
  for j in range(N):
    if (b>>j)&1 and data[i-1][j]:
      dp[b] += dp[b-(1<<j)]
      dp[b] %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
data = ILL(N)


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

dp[0][0] = 1

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

Submission status: Accepted

Solution code:
from itertools import combinations
def solve():
  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 i in range(N):
    for com in combinations(range(N),i+1):
      S = 0
      for k in com:
        S += 1<<k
      for j in com:
        dp[S] += dp[S-(1<<j)]*A[i][j]
        dp[S] %= mod
  return dp[-1]
print(solve())

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  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 i in range(1,N+1):
    for com in combinations(range(N),i):
      S = 0
      for k in com:
        S += 1<<k
      for j in com:
        if A[i-1][j]==1:
          dp[S] += dp[S-(1<<j)]
          dp[S] %= mod
  return dp[-1]
print(solve())

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  mod = 10**9+7
  dp = [[0]*(1<<N) for _ in range(N+1)]
  dp[N][0] = 1
  for i in range(N-1,-1,-1):
    for com in combinations(range(N),N-i):
      S = 0
      for k in com:
        S += 1<<k
      for j in com:
        if A[i][j]==1:
          dp[i][S] += dp[i+1][S-(1<<j)]
          dp[i][S] %= mod
  return dp[0][-1]
print(solve())

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  mod = 10**9+7
  dp = [[0]*(1<<N) for _ in range(N+1)]
  dp[N][-1] = 1
  for i in range(N-1,-1,-1):
    for com in combinations(range(N),i):
      S = 0
      for k in com:
        S += 1<<k
      for j in range(N):
        if not S>>j&1: #jがSに含まれないなら
          if A[i][j]==1:
            dp[i][S] += dp[i+1][S|(1<<j)]
            dp[i][S] %= mod
  return dp[0][0]
print(solve())

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  mod = 10**9+7
  dp = [[0]*(1<<N) for _ in range(N+1)]
  dp[N][-1] = 1
  for i in range(N-1,-1,-1):
    for com in combinations(range(N),i):
      S = 0
      for k in com:
        S += 1<<k
      for j in range(N):
        if not S>>j&1: #jがSに含まれないなら
          if A[i][j]==1:
            dp[i][S] += dp[i+1][S+(1<<j)]
            dp[i][S] %= mod
  return dp[0][0]
print(solve())

Submission status: Accepted

Solution code:
def solve():
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  mod = 10**9+7
  dp = [[0]*(1<<N) for _ in range(N+1)]
  dp[N][-1] = 1
  for S in range((1<<N)-1,-1,-1):
    i = sum([1&(S>>k) for k in range(N)])
    for j in range(N):
      if not (S>>j)&1: #jがSに含まれないなら
        if A[i][j]==1:
          dp[i][S] += dp[i+1][S+(1<<j)]
          dp[i][S] %= mod
  return dp[0][0]
print(solve())

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)

	popcount = lambda x: bin(x).count("1")
	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n)-1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and not (mask & (1 << cand)):
				nmask = mask ^ (1 << cand)
				dp[nmask] += (dp[mask] % MOD)
				dp[nmask] %= MOD
	print(dp[-1]) 
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(20000)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f

def main():
	MOD = 10**9 + 7
	n = int(rl())
	A = []
	for _ in range(n):
		row = []
		for bit in rli():
			row.append(bit)
		A.append(row)

	dp = [0 for _ in range(1 << n)]
	dp[0] = 1
	for mask in range((1 << n)-1):
		new = popcount(mask)
		for cand in range(n):
			if A[new][cand] and not (mask & (1 << cand)):
				nmask = mask ^ (1 << cand)
				dp[nmask] += (dp[mask] % MOD)
				dp[nmask] %= MOD
	print(dp[-1]) 
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import itertools

mod=10**9+7
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(2**n) for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
  for bit in range(2**n):
    if dp[i][bit]!=0:
      for j in range(n):
        if bit&(2**j)==0 and arr[i][j]==1:
          dp[i+1][bit^(2**j)]+=dp[i][bit]
          dp[i+1][bit^(2**j)]%=mod
print(dp[n][2**n-1])

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    table = [na() for _ in range(n)]

    dp = [0 for _ in range(2 ** n)]
    dp[2 ** n - 1] = 1

    for i in range(2 ** n - 1, 0, -1):
        j = n - bin(i).count("1")
        for j, val in enumerate(table[j]):
            if val:
                if i & 1 << j:
                    tmp = i ^ 1 << j
                    dp[tmp] += dp[i]
                    dp[tmp] %= MOD

    print(dp[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    table = [na() for _ in range(n)]

    dp = [0 for _ in range(2 ** n)]
    dp[2 ** n - 1] = 1

    for i in range(2 ** n - 1, 0, -1):
        j = n - format(i, "b").count("1")
        for j, val in enumerate(table[j]):
            if val:
                if i & 1 << j:
                    tmp = i ^ 1 << j
                    dp[tmp] += dp[i]
                    dp[tmp] %= MOD

    print(dp[0])


if __name__ == '__main__':
    main()

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] * (1<<N)
dp[0] = 1
for i in range(1, 1<<N):
    cnt = 0
    for j in range(N+1):cnt += (i>>j)&1
    for j in range(N):
        if (i>>j)&1 == 0: continue
        dp[i] += dp[i - (1<<j)] * A[cnt-1][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
dp = [0] * (1<<N)
dp[0] = 1
for i in range(1, 1<<N):
    cnt = bin(i).count("1")
    for j in range(N):
        if (i>>j)&1 == 0: continue
        dp[i] += dp[i - (1<<j)] * A[cnt-1][j]
        dp[i] %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:

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

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

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

    for bit in range(1 << N):
        i = bitcount[bit]
        for j in range(N):
            # i番目の男性とk番目の女性が相性○ かつ その女性がまだマッチング済みでない場合
            if ((bit >> j) & 1 == 0) and (AB[i - 1][j] == 1):
                # 今の状態からk番目の女性だけを新たにbit立てる
                dp[bit ^ (1 << j)] += dp[bit]
        dp[bit] %= MOD
    print(dp[-1])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

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

    dp = [[0] * (1 << N) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        for bit in range(1 << N):
            # 更新されている箇所は飛ばす
            if not dp[i][bit]:
                continue
            # N人の女性を見ていく
            for k in range(N):
                # i番目の男性とk番目の女性が相性○ かつ その女性がまだマッチング済みでない場合
                if AB[i][k] == 1 and (bit >> k & 1) == 0:
                    # 今の状態からk番目の女性だけを新たにbit立てる
                    dp[i + 1][(bit ^ (1 << k))] += dp[i][bit]
                    dp[i + 1][(bit ^ (1 << k))] %= MOD
    print(dp[N][(1 << N) - 1])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import math

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
a_array = naa(N)

mod = 10 ** 9 + 7
ans = [-1] * (2 ** N)


def solve(n, c):
    # print(n,c)
    # print(ans)
    if ans[n] != -1:
        return ans[n]
    ans[n] = 0
    if c == N - 1:
        ans[n] = a_array[c][int(math.log2(n))]
        return ans[n]
    for i in range(N):
        if a_array[c][i] == 0 or n & (1 << i) == 0:
            continue
        ans[n] = (ans[n] + solve(n - (1 << i), c+1)) % mod
    return ans[n]


print(solve(2**N-1, 0))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# from collections import defaultdict
# from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, data):
    FULLBIT = (1 << N) - 1
    memo = [-1] * (1 << N)

    def f(cursor, available):
        if cursor == N:
            return 1
        ret = memo[available]
        if ret != -1:
            return ret
        ret = 0
        j = 0
        m = available
        while m:
            if m & 1:
                # available woman
                if data[cursor * N + j]:
                    # acceptable
                    ret += f(cursor + 1, available ^ (1 << j))
            j += 1
            m //= 2
        ret %= MOD
        memo[available] = ret
        return ret

    return f(0, FULLBIT)


def main():
    # parse input
    N = int(input())
    data = list(map(int, read().split()))
    print(solve(N, data))


# tests
T1 = """
3
0 1 1
1 0 1
1 1 1
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    """


T2 = """
4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    1
    """


T4 = """
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
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    102515160
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

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

N = INT()
a = [LIST() for _ in range(N)]

dp = [0]*(1<<N)
dp[0] = 1
for S in range(1, 1<<N):
    i = popcount(S)
    for j in range(N):
        if (S>>j)&1 and a[i-1][j] == 1:
            dp[S] += dp[S^(1<<j)]
            dp[S] %= mod
print(dp[(1<<N)-1])

Submission status: Accepted

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8) 
    x = x + (x >> 16) 
    x = x + (x >> 32) 
    return x & 0x0000007f
f=popcount
a=[]
n=int(input())
for _ in range(n):
    a.append(tuple(map(int,input().split())))

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


dp[0]=1

for s in range(1,S):
    i=f(s)
    for j in range(n):
        if s>>j&1:
            if a[i-1][j]:
                dp[s]+=dp[s-(1<<j)]
        else:
            dp[s]%=10**9+7
            continue
# print(dp)
print(dp[S-1]%(10**9+7))

Submission status: Accepted

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
M = 10**9+7
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: Accepted

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
M = 10**9+7
from itertools import combinations
for i in range(1,n+1):
    for c in combinations(range(n), i):
        b = 0
        for item in c:
            b += 1<<item
        for item in c:
            if a[i-1][item]:
                dp[i][b] += dp[i-1][b-(1<<item)]
                dp[i][b] %= M
print(dp[n][pow(2,n)-1])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (1 << N)
dp[0] = 1
MOD = 10 ** 9 + 7
now = {0}
for _ in range(N):
    mat = [1<<i for i, v in enumerate(input().split()) if v == '1']
    nxt = set()
    for k in now:
        p = dp[k] % MOD
        for m in mat:
            if k & m: # 1101 & 0100 3番目の人はすでにペアになっているためはじく
                continue
            dp[k | m] += p # 1001 | 0010 = 1011
            nxt.add(k | m)
    now = nxt
print(dp[-1] % MOD) #dp[11...11]が答えになる

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def count_bits(N):
    T = 0
    while N != 0:
        T += N & 1
        N >>= 1
    return T


def solve():
    """
    OPT[i][j] - number of pairs for first i man, with mask j=0011..01

    OPT[i+1][j|k] += OPT[i][j] k has exactly one bit set j|k != j and i+1 is compatible with k-th woman

    """
    N = read_int()
    modulo = 10**9+7
    A = []
    for _ in range(N):
        A.append(read_ints())
    dp = [0]*(2**N)
    dp[0] = 1
    for mask in range(2**N-1):
        a = count_bits(mask)
        for b in range(N):
            if A[a][b] and mask&(1<<b) == 0:
                dp[mask|(1<<b)] = (dp[mask|(1<<b)]+dp[mask])%modulo
    return dp[-1]


if __name__ == '__main__':
    print(solve())

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]*(1<<n)
bit = [0]*(1<<n)
dp[0] = 1

for i in range(1,1<<n):
    bit[i] = bit[i//2]+i%2
    for j in range(n):
        if i >> j & 1:
            dp[i] += dp[i-(1<<j)]*a[bit[i]-1][j]
            dp[i] %= mod
print(dp[-1]%mod)

Submission status: Accepted

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
mod=10**9+7
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))