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:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


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

    return count



N=10**9 + 7
n=int(inp())
ar=[]
for i in range(n):
    ar.append(lis())
total=1<<n
bits=[[]for _ in range(n+1)]
dp=[[0 for i in range(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: Time Limit Exceeded

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


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

    return count



N=10**9 + 7
n=int(inp())
ar=[]
for i in range(n):
    ar.append(lis())
total=1<<n
bits=[[]for _ in range(n+1)]
dp=[[0 for i in range(total+5)] for j in range(n+5)]

for i in range(total+1):
    k=countSetBits(i)
    bits[k].append(i)
for i in range(n):
    if ar[0][i]==1:
        dp[0][1<<(n-1-i)]=1
for i in range(1,n):
    for j in bits[i+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: Time Limit Exceeded

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 in range(N):
        row = aff[i]
        for idx in range(N):
            if row[idx] == 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: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
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

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    return (S>>j)&1

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

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

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

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

Submission status: Time Limit Exceeded

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)
		

	@lru_cache(None)
	def dp(mask):
		new = popcount(mask)
		if new == n: return 1
		cnt = 0
		for cand in range(n):
			bcand = 1 << cand
			if A[new][cand] and not (mask & bcand):
				cnt += dp(mask ^ bcand)
				cnt %= MOD
		return cnt % MOD
	print(dp(0))
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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():
	n = int(rl())
	A = []
	for _ in range(n):
		row = 0
		for i, bit in enumerate(rli()):
			row |= (bit << i)
		A.append(row)

	subset = lambda x, y: (x & y) == x
	kth = lambda x, k: x & (1 << k)
	MOD = 10**9 + 7
	@lru_cache(None)
	def dp(i, not_matched):
		if i == n: return 1
		cnt = 0
		for j in range(n):
			if kth(not_matched, j) and kth(A[i], j):
				cnt += dp(i + 1, not_matched ^ (1 << j))
				cnt %= MOD
		return cnt % MOD

	ans = dp(0, (1 << n)-1)
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

    arr.append(l)


mask = 1 << n

dp = []

for i in range(n+1):
    temp = []
    for j in range(mask):
        temp.append(0)
    dp.append(temp)

dp[0][0] = 1
mod = 1000000007
for i in range(n):
    for j in range(mask):

        if (bin(j)[2:].count('1') == i):
            
            for k in range(n):
                if arr[i][k] == 1 and (j & 1 << k) != 1:
                    dp[i+1][j|(1 << k)] += (dp[i][j]) % mod

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
mod = int(1e9) + 7
dp = [0 for _ in range(1<<N)]
dp[0] = 1
def edpc_o(bit, cnt):
    if dp[bit]:
        return dp[bit]
    val = 0
    for i in range(N):
        if ((bit >> i) & 1) * A[cnt-1][i]:
            val += edpc_o(bit&(~(1<<i)), cnt-1) * (A[cnt-1][i])
            val %= mod
    dp[bit] = val
    return dp[bit]
x = edpc_o((1<<N)-1, N)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
#dp = [0] * (1 << n)
dp = defaultdict(int)
dp[0] = 1
for i in range(n):
    a = list(map(int, input().split()))
    #ndp = [0] * (1 << n)
    ndp = defaultdict(int)
    for j in range(n):
        if a[j] == 1:
            #for s in range(1 << n):
            for s in dp:
                if (s >> j & 1) == 0:
                    ndp[s | (1 << j)] += dp[s]
                    ndp[s | (1 << j)] %= 1000000007
    dp = ndp
print(dp[(1 << n) - 1])

Submission status: Time Limit Exceeded

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

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 = 1101
            nxt.add(k | m)
    now = nxt
print(dp[-1] % MOD) #dp[11...11]が答えになる

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

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

    dp = [[0]*(1<<N) for _ in range(N+1)]
    dp[0][0] = 1
    for iM in range(N):
        for S in range(1<<N):
            if dp[iM][S]:
                dp[iM][S] %= MOD
                for iW in range(N):
                    if S & (1<<iW) == 0 and Ass[iM][iW]:
                        S2 = S ^ (1<<iW)
                        dp[iM+1][S2] += dp[iM][S]

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


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

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

    dp = [0] * (1<<N)
    dp[0] = 1
    for S in range((1<<N)-1):
        dp[S] %= MOD
        iM = bin(S).count('1')
        for iW in range(N):
            if S & (1<<iW) == 0 and Ass[iM][iW]:
                S2 = S ^ (1<<iW)
                dp[S2] += dp[S]

    print(dp[-1] % MOD)


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

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

    dp = [0] * (1<<N)
    dp[0] = 1
    for S in range(1, 1<<N):
        iM = bin(S).count('1') - 1
        for iW in range(N):
            if S & (1<<iW) and Ass[iM][iW]:
                S0 = S ^ (1<<iW)
                dp[S] += dp[S0]
        dp[S] %= MOD

    print(dp[-1])


solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MOD = 10**9 + 7

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

    Sss = [[] for _ in range(N+1)]
    for S in range(1<<N):
        num1 = bin(S).count('1')
        Sss[num1].append(S)

    dp = [0] * (1<<N)
    dp[0] = 1
    for iM, Ss in enumerate(Sss[:-1]):
        for S in Ss:
            dp[S] %= MOD
            for iW in range(N):
                if S & (1<<iW) == 0 and Ass[iM][iW]:
                    S2 = S | (1<<iW)
                    dp[S2] += dp[S]

    print(dp[-1] % MOD)


solve()

Submission status: Time Limit Exceeded

Solution code:
def bit(n,k):
  return (n>>k)&1
def bc(x):
  return bin(x).count("1")
mod = 10**9+7
n = int(input())
a = [[] for _ in range(n)]
for i in range(n):
  ai = list(map(int,input().split()))
  a[i] = ai
m = 2**n-1
dp = [0 for _ in range(m+1)]
dp[0] = 1
for s in range(1,m+1):
  i = bc(s)
  for j in range(n):
    if bit(s,j) and a[i-1][j]:
      dp[s] = (dp[s]+dp[s^(1<<j)])%mod
print(dp[m])

Submission status: Time Limit Exceeded

Solution code:


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


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


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())
    OPT = [
        [0]*(2**N) for _ in range(1+N)
    ]
    OPT[0][0] = 1
    S = set([0])
    for i in range(N):
        new_S = set()
        for j in S:
            for k in range(N):
                if j & (1 << k) == 0 and A[i][k] == 1:
                    OPT[i+1][j|(1 << k)] = (OPT[i+1][j|(1 << k)]+OPT[i][j])%modulo
                    new_S.add(j|(1 << k))
        S = new_S
    return OPT[-1][-1]


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

Submission status: Time Limit Exceeded

Solution code:


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


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


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())
    OPT = [
        [0]*(2**N) for _ in range(1+N)
    ]
    OPT[0][0] = 1
    S = set([0])
    for i in range(N):
        #new_S = set()
        for j in range(2**N):
            for k in range(N):
                if j & (1 << k) == 0 and A[i][k] == 1:
                    OPT[i+1][j|(1 << k)] = (OPT[i+1][j|(1 << k)]+OPT[i][j])%modulo
                    #new_S.add(j|(1 << k))
        #S = new_S
    return OPT[-1][-1]


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

Submission status: Time Limit Exceeded

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


def count_bit_flag(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


def main():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    memo = {i: set() for i in range(N)}
    for bit in range(1, 1 << N):
        memo[count_bit_flag(bit)-1].add(bit)

    dp = [0] * (1 << N)
    dp[0] = 1
    for i, bit_list in enumerate(memo.values()):
        for bit in bit_list:
            for j, a in enumerate(A[i]):
                if a and (bit >> j) & 1:
                    dp[bit] += dp[bit ^ (1 << j)]
                    dp[bit] %= mod
    print(dp[(1 << N) - 1])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6+10)
def gethelp(mask1,mask2,ind):
    # print(mask1,mask2)
    global n,a,dp
   
    if dp.get(str(mask1)+' '+str(mask2),None)!=None:
        return dp[str(mask1)+' '+str(mask2)]
    dp[str(mask1)+' '+str(mask2)]=0
    for i in range(ind+1,n):
        if (mask1&(1<<i))==1:
            continue
        for j in range(n):
            if (mask2&(1<<j))==1:
                continue
            if a[i][j]==1:
                # andand (mask2&(1<<j))==0:
                # print('here ',end=' ')
                # print(i,j)
                dp[str(mask1)+' '+str(mask2)]+=gethelp(mask1|(1<<i),mask2|(1<<j),i)
    
    return dp[str(mask1)+' '+str(mask2)]
n=int(input())
a=[list() for i in range(n)]
for _ in range(n):
    a[_]=list(map(int,input().split()))
dp=dict()
dp[str((1<<n)-1)+' '+str((1<<n)-1)]=1 
# print(dp)
t=gethelp(0,0,-1)
# print(dp)/
print(t)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

N = int(input())
a = [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 j in range(2**N):
        if bin(j).count('1') == i:  # 立っている bit の数が i ならば
            for k in range(N):
                if not (j & (1<<k)) and a[i][k] == 1:
                    dp[i+1][j+(1<<k)] += dp[i][j]
                    dp[i+1][j+(1<<k)] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
li=[]
#li=[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]]

for _ in range(n):
    li.append([int(k) for k in input().split()])

ans=0
check=(n*(n+1))//2
#print(check)
mod=10**9+7
def findans(li,j,totm,totw):
    #print(totm,totw)
    global ans
    if j==n:
        if totm==check and totw==check:
            ans=(ans+1)%mod
        return
    for i in range(n):
        if li[j][i]==1:
            findans(li,j+1,totm+(j+1),totw+(i+1))
findans(li,0,0,0)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
li=[]
#li=[[0,1,0,0],[0,0,0,1],[1,0,0,0],[0,0,1,0]]

for _ in range(n):
    li.append([int(k) for k in input().split()])

ans=0
check=(n*(n+1))//2
#print(check)
mod=10**9+7
def findans(li,j,totm,totw):
    #print(totm,totw)
    global ans
    if j==n:
        if totm==check and totw==check:
            ans+=1
        return
    for i in range(n):
        if li[j][i]==1:
            findans(li,j+1,totm+(j+1),totw+(i+1))
findans(li,0,0,0)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    dp = [0 for _ in range(1 << N)]
    dp[0] = 1
    for s in range(1, 1 << N):
        man = sum(map(int, '{:b}'.format(s))) - 1  # count bits
        val = 0
        for woman in range(len('{:b}'.format(s))):
            if (s >> woman) & 1 == 0:
                continue
            if A[man][woman] == 1:
                val += dp[s - (1 << woman)]
                val %= MOD
        dp[s] += val
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def add(a, b):
    mod = 1e9+7
    c = a + b
    if c >= mod:
        c -= mod
    return c

n = int(input())

can = [[int(x) for x in input().split()] for _ in range(n)]

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

dp[0] = 1

for mask in range((1<<n)-1):
    men = bin(mask).count("1")
    
    
    for women in range(n):
        if can[men][women] == 1 and mask&(1<<women) == 0:
            m2 = mask ^ (1 << women)
            dp[m2] = add(dp[m2], dp[mask])

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

"""
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

// dp[i] - no. of ways to match this subset of women
// ans - dp[1<<n-1]
int add(int a, int b) {
    const int mod = 1e9+7;
    
    return (a+b) % mod;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
	vector<vector<int>> can(n, vector<int>(n));
	
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
	        scanf("%d", &can[i][j]);
	    }
	}
	
	vector<int> dp(1<<n);
	
	dp[0] = 1;
	
	for (int mask = 0; mask < (1<<n)-1; mask++) {
	    int men = __builtin_popcount(mask);
	    for (int women = 0; women < n; women++) {
	        if (can[men][women] && !((1<<women)&mask)) {
	            int m2 = mask ^ (1<<women);
	            dp[m2] = add(dp[m2], dp[mask]);
	        }    
	    }
	}
	
	printf("%d\n", dp[(1<<n)-1]);
	
	return 0;
}
"""

Submission status: Time Limit Exceeded

Solution code:
def add(a, b):
    mod = 1e9+7
    return (a+b)%mod

n = int(input())

can = [[int(x) for x in input().split()] for _ in range(n)]

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

dp[0] = 1

for mask in range((1<<n)-1):
    men = bin(mask).count("1")
    
    
    for women in range(n):
        if can[men][women] == 1 and mask&(1<<women) == 0:
            m2 = mask ^ (1 << women)
            dp[m2] = add(dp[m2], dp[mask])

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

"""
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

// dp[i] - no. of ways to match this subset of women
// ans - dp[1<<n-1]
int add(int a, int b) {
    const int mod = 1e9+7;
    
    return (a+b) % mod;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
	vector<vector<int>> can(n, vector<int>(n));
	
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
	        scanf("%d", &can[i][j]);
	    }
	}
	
	vector<int> dp(1<<n);
	
	dp[0] = 1;
	
	for (int mask = 0; mask < (1<<n)-1; mask++) {
	    int men = __builtin_popcount(mask);
	    for (int women = 0; women < n; women++) {
	        if (can[men][women] && !((1<<women)&mask)) {
	            int m2 = mask ^ (1<<women);
	            dp[m2] = add(dp[m2], dp[mask]);
	        }    
	    }
	}
	
	printf("%d\n", dp[(1<<n)-1]);
	
	return 0;
}
"""

Submission status: Time Limit Exceeded

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

if __name__=="__main__":
    main()