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:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return

#E
def E():
    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [[0]*m for i in range(n+1)]
    dp[0][0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    d = [set() for i in range(n+1)]
    d[0] = set([0])
    for i in range(n):
        ni = i+1
        for k in d[i]:
            for j in a[i]:
                bj = 1<<j
                if k&bj:
                    continue
                nk = k|bj
                dp[ni][nk] += dp[i][k]
                dp[ni][nk] %= mod
                d[ni].add(nk)
    print(dp[n][m-1])
#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Time Limit Exceeded

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

MOD = 1e9+7

n = int(input())
a = [[0]*n for i in range(n)]

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

dp = [-1]*((1<<21)+1)

# sys.exit(0)

def solve(i, mask):
    if (i==n):
        return 1

    if (dp[mask]!=-1):
        return dp[mask]
    
    ans = 0
    for j in range(n):
        if a[i][j]==1 and (mask&(1<<j))==0:
            ans = (ans+solve(i+1, mask|(1<<j)))%MOD

    dp[mask]=ans
    return ans

print(int(solve(0, 0)))

Submission status: Time Limit Exceeded

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

MOD = 1e9+7

n = int(input())
a = [[0]*n for i in range(n)]

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

dp = [[-1]*((1<<21)+1) for i in range(n)]

# sys.exit(0)

def solve(i, mask):
    if (i==n):
        return 1

    if (dp[i][mask]!=-1):
        return dp[i][mask]
    
    ans = 0
    for j in range(n):
        if a[i][j]==1 and (mask&(1<<j))==0:
            ans = (ans+solve(i+1, mask|(1<<j)))%MOD

    dp[i][mask]=ans
    return ans

print(int(solve(0, 0)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 **9 + 7



n = int(input())
match_list = []
for i in range(n):
    match_list.append(list(map(int, input().split())))
    
    
c = [0]
for i in range(n):
    c += [j+1 for j in c]


dp = [0] * (1 << n)
dp[0] = 1
for i in range((1 << n)-1):
    for j in range(n):
        if match_list[c[i]][j]:
            dp[(1<<j)^i] = (dp[(1<<j)^i] + dp[i])%mod


print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

n = int(input())

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


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)
            r %= mod
    memo[state] = r
    return r


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

Submission status: Time Limit Exceeded

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

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

bit_to_i = {1<<i:i for i in range(N)}
  
dp = [0] * (1<<N)
dp[0] = 1

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

answer = dp[-1]
print(answer)

Submission status: Time Limit Exceeded

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

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

dp = np.zeros(1<<N, dtype=np.uint32)
dp[0] = 1

for A_row in A:
    prev = dp.copy()
    dp = np.zeros_like(prev)
    for n,a in enumerate(A_row):
        if a == 0:
            continue
        x = 1<<n
        dp = dp.reshape(-1,2*x)
        prev = prev.reshape(-1,2*x)
        dp[:,x:] += prev[:,:-x]
        dp = dp.ravel()
        prev = prev.ravel()
        dp[dp >= MOD] -= MOD

answer = dp[-1]
print(answer)

Submission status: Time Limit Exceeded

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

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

dp = np.zeros(1<<N, dtype=np.int64)
dp[0] = 1

for A_row in A:
    prev = dp.copy()
    dp = np.zeros_like(prev)
    for n,a in enumerate(A_row):
        if a == 0:
            continue
        x = 1<<n
        dp = dp.reshape(-1,2*x)
        prev = prev.reshape(-1,2*x)
        dp[:,x:] += prev[:,:-x]
        dp = dp.ravel()
        prev = prev.ravel()
    dp %= MOD

answer = dp[-1]
print(answer)

Submission status: Time Limit Exceeded

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

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

dp = np.zeros(1<<N, dtype=np.int64)
dp[0] = 1

for A_row in A:
    prev = dp.copy()
    dp = np.zeros_like(prev)
    for n,a in enumerate(A_row):
        if a == 0:
            continue
        x = 1 << n
        dp[x:] += prev[:-x]
    dp %= MOD

answer = dp[-1]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
# @author 

import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        MOD = 10 ** 9 + 7

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

        dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        by_1 = defaultdict(list)
        for j in range(1 << n):
            by_1[bin(j).count('1')].append(j)
            
        for i in range(1, n + 1):
            for j in by_1[i - 1]:
                for k in range(n):
                    if (j >> k) & 1 or a[i - 1][k] == 0:
                        continue
                    dp[i][j | (1 << k)] += dp[i - 1][j]
                    dp[i][j | (1 << k)] %= MOD

        # [print(item) for item in dp]

        print(sum(dp[n]))

solver = OMatching()
input = sys.stdin.readline

solver.solve()

Submission status: Time Limit Exceeded

Solution code:
# @author 

import sys

class OMatching:
    def solve(self):
        from collections import defaultdict

        MOD = 10 ** 9 + 7

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

        dp = [[0] * ((1 << n) + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        by_1 = defaultdict(set)
        for j in range(1 << n):
            by_1[bin(j).count('1')].add(j)
        for i in range(1, n + 1):
            for j in by_1[i - 1]:
                for k in range(n):
                    if (j >> k) & 1 or a[i - 1][k] == 0:
                        continue
                    dp[i][j | (1 << k)] += dp[i - 1][j]
                    dp[i][j | (1 << k)] %= MOD

        # [print(item) for item in dp]

        print(sum(dp[n]))

solver = OMatching()
input = sys.stdin.readline

solver.solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = []
mod = 10 ** 9 + 7
dp = [-1] * (2 ** N)
#dp[n]: 考慮する女の組みを二進数で表す。考慮する男は前から女の数番目まで。そのときの組み合わせ数。
dp[0] = 1
stack = [0]
next_stack = []

for _ in range(N):
	a.append(list(map(int, input().split())))
	
for i in range(N):
	while stack:
		n = stack.pop()
		tmp = n
		for j in range(N):
			r = tmp % 2
			if r == 0 and dp[n + (2 ** j)] == -1:
				next_stack.append(n + 2 ** j)
				dp[n + (2 ** j)] = a[i][j] * dp[n]
			elif r == 0 and dp[n + (2 ** j)] != -1:
				dp[n + (2 ** j)] += a[i][j] * dp[n]
				dp[n + (2 ** j)] %= mod
				
			tmp = tmp // 2
				
	stack = copy.copy(next_stack)
	next_stack = []
	
print(dp[-1])

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

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

dp = [0] * (1 << N)
# ペアを１つも作っていない状態: 1通り
dp[0] = 1

for S in range(0,1 << N):
    # 男性 1,...,iまでが既にペアができている
    i = bin(S).count("1")
    for j in range(1,N+1):
        # 男性iとペアを作れる女性jはa[i-1][j-1] = 1を満たす
        # iまでペアを作ったとき,集合Sにjが含まれている必要がある
        # S >> (j-1) & 1で Sのj桁目に1が立っているか判定
        if A[i-1][j-1] == 1 and S >> (j-1) & 1 == 1:
            # 男性iと女性jでペアを作る直前の集合にはjが含まれないので
            # jを取り除く必要がある
            # S ^ (1<<(j-1)) でj桁目を0にすることができる
            dp[S] += dp[S^(1 << (j-1))]
            dp[S] %= mod

# 全てのペアができたとき全ての桁に1が立っているので(1 << N) - 1で表現できる
ans = dp[(1 << N) - 1]
print(ans)

Submission status: Time Limit Exceeded

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

def bac(ju):
    ans=0
    di=1
    for i in range(n):
        if ju[i]:
            ans+=di
        
        d*=2
    return ans

def ch (k):
    ju=[0 for i in range(n)]
    for i  in range(n):
        ju[i]=k%2
        k//=2
    return ju

mo=[1 for i in range(n)]
for i in range(n-1):
    mo[i+1]=mo[i]*2
x=2**n
dp=[0 for i in range(x)]
dp[0]=1
for i in range(1,x):
    ju=ch(i)
    co=-1
    me=0
    gg=0
    for j in range(n):
        if ju[j]:
            gg+=mo[j]
            co+=1
    for j in range(n):
        if ju[j] and da[co][j]:
            me+=dp[gg-mo[j]]
    dp[i]=me%1000000007
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
import fileinput


def solve_match(match_matrix):
    size = len(match_matrix)
    combo_dict = {}

    r = tuple(range(size))

    for col in range(size):
        for combo in itertools.combinations(r, col + 1):
            if col == 0:
                combo_dict[combo] = match_matrix[combo[0]][col]
            else:
                s = 0
                for i, row_num in enumerate(combo):
                    if match_matrix[row_num][col] == 1:
                        s += combo_dict[combo[:i] + combo[i + 1:]]
                combo_dict[combo] = s
    return combo_dict[r]


inp = fileinput.FileInput()
n = int(inp.readline())

arr = []
for _ in range(n):
    arr.append([int(v) for v in inp.readline().split(" ")])

print(solve_match(arr))

Submission status: Time Limit Exceeded

Solution code:
def calcdp(i, s):
    # i番目の男性まで評価しときに、女性のマッチング状態がsとなる組み合わせの数
    global dp, MOD, N, A
    if dp[i][s] != -1:
        return dp[i][s]
    
    r = 0
    for j in range(N):
        if A[i-1][j] and s & (1 << j):
            r += calcdp(i - 1, s ^ (1 << j))
    
    r = r % MOD
    dp[i][s] = r
    return r


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

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

print(calcdp(N, 2**N-1))

Submission status: Time Limit Exceeded

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

def itercomb(n,k):
    _a = 2**k-1
    yield _a
    _ALL=2**n
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

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

dp = [0]*(2**n)
dp[0] = 1
"""
for m in range(1,n+1):
    for a in itercomb(n,m):
        dp[a] = sum(dp[a^2**c] for c in range(n) if 2**c&a and A[m-1][c])%MOD

for a in range(1,2**n):
    m=bin(a).count("1")
    dp[a] = sum(dp[a^2**c] for c in range(n) if 2**c&a and A[m-1][c])%MOD


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

for m in range(1,n+1):
    for a in itercomb(n,m):
        ans=0
        for c in range(n):
            if 2**c&a and A[m-1][c]:
                ans += dp[a^2**c]
                ans%=MOD
        dp[a] = ans

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


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def itercomb(n,k):
    _a = 2**k-1
    yield 2**k-1
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= 2**n: break
        yield _a

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

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

for m in range(1,n+1):
    for a in itercomb(n,m):
        #print(a)
        #if bin(a).count("1") != m: continue
        dp[a] = sum(dp[a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def itercomb(n,k):
    _a = 2**k-1
    yield 2**k-1
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= 2**n: break
        yield _a

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

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        #print(a)
        #if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
class comb(object):
    def __init__(self, n,k):
        self._i = 2**k-1
        self._ans = 0
    def __iter__(self):
        # __next__()はselfが実装してるのでそのままselfを返す
        return self
    def __next__(self):  # Python2だと next(self) で定義
        if self._i >= 2**n:
            raise StopIteration()
        self._ans = self._i
        x = self._i & -self._i
        y = self._i + x
        self._i = (((self._i & ~y) // x) >> 1) | y
        return self._ans


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

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in comb(n,m):
#        print(a)
        #if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in range(2**n):
        if bin(a).count("1") != m: continue
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [[0]*(2**n) for i in range(n+1)]
dp[0][0] = 1
for m in range(1,n+1):
    for a in range(2**n):
        dp[m][a] = sum(dp[m-1][a-2**c] for c in range(n) if 2**c&a != 0 and A[m-1][c]==1)%MOD


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

npow = 1 << n

A = [1<<j for j in range(n)]
masks = [[mask + jpow for mask in range(npow) if not mask & jpow] for jpow in A]

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

Submission status: Time Limit Exceeded

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

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

npow = 1 << n

A = [1<<j for j in range(n)]
masks = [[mask for mask in range(npow) if not mask & jpow] for jpow in A]

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

Submission status: Time Limit Exceeded

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

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

npow = 1 << n

A = [1<<j for j in range(n)]
masks = [[mask for mask in range(npow) if not mask & jpow] for jpow in A]

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

Submission status: Time Limit Exceeded

Solution code:
range = xrange
input = raw_input
MOD = 10**9+7

def main():
    n = int(input())

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

    npow = 1 << n

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

    print(sum(dp) % MOD)

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

def main():
    n = int(input())

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

    npow = 1 << n

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

    print(sum(dp) % MOD)

main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO as BytesIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

BUFSIZE = 8192
MOD = 10**9 + 7


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        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):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    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)


input = FastIO(sys.stdin).readline


def main():
    n = int(input())

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

    for i in range(n - 1):
        _dp = [0] * (1 << n)
        for j in [i // 2 for i, x in enumerate(input()) if x == '1']:
            for mask in range(1 << n):
                if not mask >> j & 1:
                    _dp[mask + (1 << j)] += dp[mask]
        for mask in range(1 << n):
            _dp[mask] %= MOD
        dp = _dp

    os.write(1, str(sum(dp) % MOD))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

mod = pow(10,9)+ 7

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

dp = [0 for i in range(1<<n)]
dp[0] = 1
for i in range(1<<n):
    count = 0
    for j in range(n):
        if((i&(1<<j))):
            count += 1
    for j in range(n):
        if( (i&(1<<j)) == 0):
            if(arr[count][j] == 1):
                dp[i|(1<<j)] = (dp[i|(1<<j)] + dp[i])%mod


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

Submission status: Time Limit Exceeded

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 1000000007
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

bit = lambda s, j: (s >> j) & 1

def f(n, a):
    mod = int(1e9 + 7)
    sn = 1 << n
    dp = [[0] * sn for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        dpi = dp[i]
        dpi1 = dp[i + 1]
        ai = a[i]
        for s in range(0, sn):
            if dpi[s]:
                for j in range(n):
                    if bit(s, j) == 0 and ai[j]:
                        s_ = s | 1 << j
                        dpi1[s_] += dpi[s]
                        if dpi1[s_] > mod:
                            dpi1[s_] -= mod
    return(dp[-1][-1])

n = int(input()) # 1 <= n <= 21
a = [list(map(int, input().split())) for _ in range(n)]
print(f(n, a))

Submission status: Time Limit Exceeded

Solution code:
"""
O - Matching

考え方:
    1 ～ 2^N までの数値を用意し, それぞれの状態を 1 ～ b' 番目までの男性がマッチング完了した状態と定義する.
    この時, b' は n' を2進数で表した時の 1 bit の和とする.
    また, n' の i 桁目のビットが 1 であれば i 番目の女性はマッチング済みとする.
    ここで n' の状態が X 件成立する場合, n'' = b' + 1 を満たすすべての n に対して, n' から新たに増えたビット部分の女性とマッチングが可能であれば n'' でも X 成立するといえる.
    これを連続して計算することで最終的にすべての男女がマッチングする組み合わせの件数が求められる.

提出1回目:
    速度不足. 何か例外的なパターンではじかれた模様.
    もっと早い言語で書き直したほうがいいのだろうか...
    あとどんなパターンだとだめなのかわからん...
提出2回目:
    初期値(マッチング対象無しの場合)を 1 とすることで, 初期値の bit count 処理を省略.
    1回目ではじかれたのはおそらく N = 1, 相性 1 のパターン(1回目だと出力が 0 だった).
    これでもN=21の時には速度的にアウトっぽいけど一応提出してみよう.
    

"""


def solve():
    # データ読込
    N = int(input())
    compatibility = [[int(i) for i in input().split()] for _ in range(N)]
    # dp のデータ格納用配列の作成
    dp = [0] * (2 ** N)  # 初期値は 0(件)
    dp[0] = 1
    # 配列をループ
    for i in range(len(dp) - 1):
        man_num = bin(i).count('1')
        # 現状に1組追加したパターンに組み合わせ数を追加
        if dp[i] == 0:
            continue
        for j in range(N):
            if (i >> j) % 2 != 1:
                if compatibility[man_num][j] == 1:
                    dp[i | (2 ** j)] += dp[i]

    # 結果出力
    print(dp[-1] % (10 ** 9 + 7))
    pass


if __name__ == '__main__':
    solve()

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)] * A[i][j] for j in range(n)) % p

print(DP[-1])