Problem:


Score : 100 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 21

a_{i, j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
0 1 1
1 0 1
1 1 1

Sample Output 1

3

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

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

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

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

Sample Input 2

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

Sample Output 2

1

There is one way to make pairs, as follows:

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

Sample Input 3

1
0

Sample Output 3

0

Sample Input 4

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

Sample Output 4

102515160

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



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


Sample output:
3

Submission status: Accepted

Solution code:
def 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):
        women_list = [w for w in range(N) if (s >> w) & 1 == 1]
        man = len(women_list) - 1
        val = 0
        for woman in women_list:
            val += A[man][woman] * dp[s - (1 << woman)]
        val %= MOD
        dp[s] += val
    print(dp[(1 << N) - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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=[j for j in range(N) if i>>j &1==1]
        for j in m:
            dp[i]+=dp[i-2**j]*a[len(m)-1][j]
        dp[i]%=mod
    
    print(dp[-1])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

for state in range(2 ** N - 1):
    a = A[bin(state).count("1")] & ~state
    for j in range(N):
        if a & (1 << j):
            dp[state | (1 << j)] += dp[state]

print(dp[-1] % mod)

Submission status: Accepted

Solution code:
import numpy as np

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

MOD = 10 ** 9 + 7
dp = np.zeros(1 << N, dtype=np.int64)
dp[0] = 1
for a in A:
    new_dp = np.zeros_like(dp)
    for i in a:
        x = (1 << i)
        new_dp[x:] += dp[:-x]
    dp = new_dp
    dp %= MOD
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from itertools import product
def main():
    n=int(input())
    A=[[int(_) for _ in input().split()] for i in range(n)]
    dp=[0]*(1<<n)
    dp[0]=1
    mod=10**9+7
    for s in range(1<<n):
        i=bin(s).count("1")
        for j in range(n):
            if (s>>j)&1 and A[i-1][j]==1:
                dp[s]=(dp[s]+dp[s^(1<<j)])%mod
    print(dp[(1<<n)-1])

if __name__=='__main__':
    main()

Submission status: Accepted

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

dp = [0] * (1 << N)
dp[0] = 1
for b in range(1, 1 << N):
    i = bin(b).count('1')
    for x in range(N):
        if (b >> x) & 1 and A[i - 1][x]:
            dp[b] += dp[b ^ (1 << x)]
    dp[b] %= MOD
print(dp[-1])

Submission status: Accepted

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

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

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

# 配るDP
for bit in range((1 << n) - 1):
    i = bitcount[bit]
    for j in range(n):
        if (a[i][j] == 1) and ((bit >> j) & 1 == 0):
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[-1])

Submission status: Accepted

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

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

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

# 集めるDP
for bit in range(1,1 << n):
    i = bitcount[bit]
    for j in range(n):
        if (bit >> j) & 1 and a[i - 1][j] :
            dp[bit] += dp[bit ^ (1 << j)]
    dp[bit] %= mod
print(dp[(1 << n) - 1])

Submission status: Accepted

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

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

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

# 配るDP # TLE
for bit in range((1 << n) - 1):
    i = bitcount[bit]
    for j in range(n):
        if a[i][j] and ((bit >> j) & 1 ^ 1):
            newbit = bit | (1 << j)
            dp[newbit] += dp[bit]
            dp[newbit] %= mod
print(dp[(1 << n) - 1])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

for bit in range(1,1 << n):
    i = bin(bit).count('1')
    for j in range(n):
        if (bit >> j) & 1 and a[i - 1][j] :
            dp[bit] += dp[bit ^ (1 << j)]
    dp[bit] %= mod
print(dp[(1 << n) - 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):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
saidai = pow(2, n)
dp = [0] * saidai
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (saidai + 1)
for s in range(saidai):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[saidai - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
saidai = pow(2, n)
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (saidai + 1)
for s in range(saidai):
    # otoko = bin(s).count("1")
    # bitcnt[s] = bitcnt[s // 2] + s % 2
    i = popcnt(s)
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[saidai - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (pow(2, n))
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (pow(2, n) + 1)
for s in range(pow(2, n)):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[pow(2, n) - 1])

Submission status: Accepted

Solution code:
import sys
MOD = 10 ** 9 + 7
LI = lambda: [int(x) for x in sys.stdin.readline().split()]
NI = lambda: int(sys.stdin.readline())


def main():
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    N = NI()
    a = [LI() for _ in range(N)]
    dp = [[0] * (2**N) for _ in range(N)]

    q = [[] for _ in range(N)]
    b = 1
    for i in range(N):
        if a[0][i]:
            dp[0][b] = 1
            q[0].append(b)
        b <<= 1

    for i in range(1,N):
        for k in q[i-1]:
            v = dp[i-1][k]
            b = 1
            for l in a[i]:
                if l and k & b == 0:
                    m = k | b
                    if dp[i][m] == 0: q[i].append(m)
                    dp[i][m] = (dp[i][m] + v) % MOD
                b <<= 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    popcount_to_state = [[] for _ in range(n + 1)]
    for U in range(1 << n):
        popcount_to_state[bin(U).count('1')].append(U)

    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        A = tuple(map(int, input().split()))
        for j in range(n):
            if not A[j]:
                continue
            for U in popcount_to_state[i]:
                if (U >> j) & 1:
                    continue
                nU = U | 1 << j
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    print(dp[-1])
resolve()

Submission status: Accepted

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

    def popcount(x):
        # 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

    dp = [[0]*(1 << N) for i in range(N+1)]
    dp[0][0] = 1
    mod = 10**9+7
    for j in range(1, 1 << N):
        i = popcount(j)
        DP = dp[i]
        prev = dp[i-1]
        for k in range(N):
            if (j >> k) % 2 == 1:
                if a[i-1][k] == 1:
                    DP[j] += prev[j ^ (1 << k)]
                    DP[j] %= mod

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


main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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


def dfs(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 += dfs(bit ^ (1 << j), i + 1)
    dp[bit] = tmp % mod
    return dp[bit]


print(dfs(2 ** n - 1, 0))

Submission status: Accepted

Solution code:
mod = 10**9+7

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

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


def dfs(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 += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]


print(dfs(2**n-1, 0))

Submission status: Accepted

Solution code:
n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
mod=pow(10,9)+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1<<n):
    cnt=0
    v=[]
    #　bitが何個たつか調べる
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
            v.append(j)
    for j in v:
        dp[i] += dp[i ^ (1 << j)] * a[j][cnt-1]

print(dp[-1]%mod)

Submission status: Accepted

Solution code:


n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
mod=pow(10,9)+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1<<n):
    cnt=0
    v=[]
    #　bitが何個たつか調べる
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
            v.append(j)
    for j in v:
        dp[i] += dp[i ^ (1 << j)] * a[j][cnt-1]
        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=pow(10,9)+7
dp=[0]*(1<<n)
dp[0]=1
for i in range(1<<n):
    cnt=0
    #　bitが何個たつか調べる
    for j in range(n):
        if (i>>j)&1:
            cnt+=1
    for j in range(n):
        if (i >> j) & 1:
            dp[i] += dp[i ^ (1 << j)] * a[j][cnt-1]
            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)]
p = 10**9+7
DP = [-1 for s in range(1<<n)]
DP[0] = 1
def dp(s, l):
    if DP[s] != -1:
        return DP[s]
    tmp = 0
    for i in range(n):
        if s & (1<<i) and A[l-1][i]:
            tmp += dp(s & ~(1<<i), l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1<<n)-1, n))

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int, input().split())) for i in range(n)]
p = 10**9+7
DP = [-1 for s in range(1 << n)]
DP[0] = 1
def dp(s, l):
    if DP[s] != -1:
        return DP[s]
    tmp = 0
    for i in range(n):
        if s & (1 << i) and A[l-1][i]:
            tmp += dp(~(1 << i) & s, l-1)
    DP[s] = tmp % p
    return DP[s]
print(dp((1 << n)-1, n))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    A = [[j for j in range(n) if A[i][j]] for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in A[l-1]:
            if (1 << i) & s:
                DP[s] = (DP[s]+DP[~(1 << i) & s]) % p
    print(DP[(1 << n)-1])
main()

Submission status: Accepted

Solution code:
N = int(input())
A=[0]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
from itertools import groupby, accumulate, product, permutations, combinations
def solve(N,A):
    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 c in com:
                s += 1<<c
            for rem in com:
                dp[s] += dp[s-(1<<rem)] * A[i-1][rem]
                dp[s] %= mod
    ans = dp[-1]
    return ans
print(solve(N,A))

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):
  # 既にペアになった女性の集合がS⇔S人目までチェック済み
  k=bin(i).count("1")
  for j in range(n):
    if i&(1<<j) and a[k-1][j]:
      dp[i]+=dp[i^(1<<j)]
  dp[i]%=mod
print(dp[(1<<n)-1])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = [list(map(int, input().split())) for i in range(n)]
    p = 10**9+7
    DP = [0 for s in range(1 << n)]
    DP[0] = 1
    for s in range(1, 1 << n):
        l = bin(s).count('1')
        for i in range(n):
            if ((1 << i) & s) * A[l-1][i]:
                DP[s] += DP[~(1 << i) & s]
    print(DP[(1 << n)-1] % p)


main()

Submission status: Accepted

Solution code:
# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
mod=10**9+7
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    k=bin(i).count("1")
    # k-1人目までは確定
    for j in range(n):
        if i>>j&1 and a[k-1][j]:
            dp[i]+=dp[i^(1<<j)]
    dp[i]%=mod
print(dp[(1<<n)-1])

Submission status: Accepted

Solution code:
# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
mod=10**9+7
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[0]*(1<<n)
dp[0]=1
for i in range(1,1<<n):
    k=bin(i).count("1")
    for j in range(n):
        if i>>j&1 and a[k-1][j]:
            dp[i]+=dp[i^(1<<j)]
    dp[i]%=mod
print(dp[(1<<n)-1])

Submission status: Accepted

Solution code:
# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
mod=10**9+7
def main():
    n=int(input())
    a=[list(map(int,input().split())) for i in range(n)]
    dp=[0]*(1<<n)
    dp[0]=1
    for i in range(1,1<<n):
        k=bin(i).count("1")
        for j in range(n):
            if i>>j&1 and a[k-1][j]:
                dp[i]+=dp[i^(1<<j)]
        dp[i]%=mod
    print(dp[(1<<n)-1])
main()

Submission status: Accepted

Solution code:
# bitDP(集合を数に変換して状態(=添字)として持つようなDPのこと)
# dp[i][S]=(男性はi人目までで、既にペアになった女性の集合がSであるような場合の数)
# 「既にペアになった女性の集合がS」なら「bitpopcount(S)人目までをチェックした」ってことになるから、iを状態として持つ必要は無いことがわかる
import sys
input = sys.stdin.readline
mod=10**9+7
def main():
    n=int(input())
    a=[list(map(int,input().split())) for i in range(n)]
    dp=[0]*(1<<n)
    dp[0]=1
    for i in range(1,1<<n):
        k=bin(i).count("1")
        for j in range(n):
            if i>>j&1 and a[k-1][j]:
                dp[i]=(dp[i]+dp[i^(1<<j)])%mod
    print(dp[(1<<n)-1])
main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=[[] for _ in range(N)]
    for i in range(N):
        a[i]=LI()
    
    #dp[S]は状態Sから何通りあるか？男性は1から順に，女性マッチング情報がS   
    M=pow(2,N) 
    dp=[0]*M
    dp[0]=1
    
    def bit_cnt(num):
        cnt=0
        for i in range(N+3):
            if num&1:
                cnt+=1
            num=num>>1
        return cnt

    
    for S in range(M-1):
        if dp[S]==0:
            continue
        man=bit_cnt(S)
        for i in range(N):
            if (S>>i)&1==0:#i桁目が立っていない
                if a[man][i]==1:
                    dp[S+(1<<i)]+=dp[S]
                    dp[S+(1<<i)]%=mod
                        
        
    
    print(dp[-1])

                    
                    
    
        
    

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=[[] for _ in range(N)]
    for i in range(N):
        a[i]=LI()
    
    #dp[S]は状態Sから何通りあるか？男性は1から順に，女性マッチング情報がS   
    M=pow(2,N) 
    dp=[0]*M
    dp[0]=1
    
    def bit_cnt(N):
        B=bin(N)
        return B.count("1")

    
    for S in range(M-1):
        if dp[S]==0:
            continue
        man=bit_cnt(S)
        for i in range(N):
            if (S>>i)&1==0:#i桁目が立っていない
                if a[man][i]==1:
                    dp[S+(1<<i)]+=dp[S]
                    dp[S+(1<<i)]%=mod
                        
        
    
    print(dp[-1])

                    
                    
    
        
    

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=[[] for _ in range(N)]
    for i in range(N):
        a[i]=LI()
    
    #dp[S]は状態Sから何通りあるか？男性は1から順に，女性マッチング情報がS   
    M=pow(2,N) 
    dp=[0]*M
    dp[0]=1
    p=[1]*(N+3)
    for i in range(N+2):
        p[i+1]=p[i]*2


    def make(L):
        #itertoolsのリストから整数を生成
        res=0
        for i in range(len(L)):
            res+=p[L[i]]
        return res

    import itertools
    
    for man in range(N):
        for ite in itertools.combinations(range(N),man):
            S=make(ite)
            if dp[S]==0:
                continue
            for i in range(N):
                if (S>>i)&1==0:#i桁目が立っていない
                    if a[man][i]==1:
                        dp[S+(1<<i)]+=dp[S]
                        dp[S+(1<<i)]%=mod
                        
        
    
    print(dp[-1])

                    
                    
    
        
    

main()

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

for i in range(n):
    dp2 = [0] * (1 << n)
    for j in range(1 << n):
        if dp[j] == 0:
            continue
        for k in range(n):
            if (j >> k) & 1 == 0:
                dp2[j | (1 << k)] += dp[j] * a[i][k]
                dp2[j | (1 << k)] %= mod
    dp = dp2

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

mod = 10**9+7

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

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

Submission status: Accepted

Solution code:
mod = 10**9+7
N = int(input())
li = [list(map(int, input().split())) for i in range(N)]
lc = [0] * (1<<N)
dp = [0]*(1<<N)
dp[0] = 1
for S in range(1, 1<<N):
    lc[S] = lc[S>>1]+S%2
    for i in range(N):
        if S>>i&li[lc[S]-1][i] == 1:
            dp[S] = (dp[S]+dp[S-(1<<i)]) %mod
print(dp[(1<<N)-1])

Submission status: Accepted

Solution code:
#EDPC-O Matching
"""
bit DP
集合Sを、(s>>i)&1==1とした時,i番目の女性はマッチング済であるとし、男をループさせる。
dp[i] = 集合iから始めた場合の数(既にi状態のマッチングが終わっている場合の数)
"""
import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
n = int(readline())
mens = []
for i in range(n):
    s = readline().rstrip().decode('utf-8')
    s = "".join(s.split(" "))
    res = int(s,2)
    mens.append(res)

dp = [-1 for _ in range(1<<n)]
dp[-1] = 1 #全マッチングが終わった時、+1する為
def rec(s,v): #使用済みの集合、今の深さ
    if dp[s] != -1: #既に確定しているなら
        return dp[s]
    res = 0
    for u in range(n): #それぞれの女性について
        #その女性がマッチング済でないかつ、vと相性がいいなら
        if s>>u&1==0 and mens[v]>>u&1==1:
            res += rec(s|(1<<u),v+1)
    dp[s] = res%mod
    return dp[s]
        
print(rec(0,0))

Submission status: Accepted

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

def dfs(state, a):
    if a == N:
        if state == (1 << N) - 1:
            return 1
        else:
            return 0
    if dp[state] != -1:
        return dp[state]
    res = 0
    for i in range(N):
        if ((state >> i) & 1 == 0) and A[a][i] == 1:
            res += dfs(state | (1 << i), a + 1)
            res %= mod
    dp[state] = res
    return dp[state]

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split(" "))))
dp = [-1 for i in range((1 << N))]

print(dfs(0, 0))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

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

memo = [-1] * 2**N
memo[0] = 1

def dfs(bit_state, matched):
    if memo[bit_state] != -1:
        return memo[bit_state]
    r = 0
    for i in range(N):
        if bit_state & (1 << i) and A[matched][i]: # bitでi桁目の女性未マッチング かつ 男性がi桁目の女性に対し相性OK
            r += dfs(bit_state ^ (1 << i), matched+1) # i桁目の女性をマッチング済にして遷移
    r %= MOD
    memo[bit_state] = r
    return r

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

Submission status: Accepted

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

dp[0] = 1

bitcnt = [0] * (2**n)

def who(s):
    ans = []
    i = 0
    while s > 0:
        if s%2:
            ans.append(i)
        i += 1
        s = s >> 1
    return ans

for i in range(1,2**n):
    bitcnt[i] = bitcnt[i >> 1] + i%2
    for l in who(i):
        dp[i] += dp[i - 2**l] * a[bitcnt[i] - 1][l]
        dp[i] %= mod
print(dp[2**n - 1])

Submission status: Accepted

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0]*(1<<N)

    for i in range(N):
        use = [0]*((1<<N)+1)
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0]*((1<<N)+1) for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    a = [[int(_) for _ in input().split()] for _ in range(N)]
    MOD = 10**9+7
    
    dp = [[0]*((1<<N)+1) for _ in range(N+1)]
    dp[0][0] = 1

    for i in range(N):
        for s in range(1<<N):
            if dp[i][s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    dp[i+1][s|jb] += dp[i][s]
    
    print(dp[-1][(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

for i in range(N):
    for s in range(1<<N):
        if dp[i][s] == 0:continue
        for j in range(N):
            jb = 1<<j
            if not (s&jb) and a[i][j]:
                dp[i+1][s|jb] += dp[i][s]
    
print(dp[N][(1<<N)-1]%MOD)

Submission status: Accepted

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s|jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    a = [list(map(int,input().split())) for _ in range(N)]
    MOD = 10**9+7
    
    dp = [1] + [0 for _ in range(1<<N)]

    for i in range(N):
        use = [0 for _ in range((1<<N)+1)]
        for s in range(1<<N):
            if dp[s] == 0:
                continue
            for j in range(N):
                jb = 1<<j
                if not (s&jb) and a[i][j]:
                    use[s^jb] += dp[s]
        dp = use
    
    print(dp[(1<<N)-1]%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
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 t in range(N):
  for c in combi([x for x in range(N)], t):
    x = 0
    table = [0] * N
    for i in c:
      x += 1 << i
      table[i] = 1
    for i in range(N):
      if table[i]: continue
      if a[t][i]:
        tt = 1 << i
        dp[x + tt] += dp[x]
        dp[x + tt] %= mod
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
to = [[] for _ in range(N)]

for i in range(N):
    a = list(map(int, input().split()))
    
    for j in range(N):
        if a[j]==1:
            to[i].append(j)
    
dp = [0]*(1<<N)
dp[0] = 1
MOD = 10**9+7

for i in range((1<<N)-1):
    c = 0
    
    for j in range(N):
        if (i>>j)&1:
            c += 1
    
    for j in to[c]:
        if not (i>>j)&1:
            dp[i|(1<<j)] += dp[i]
            dp[i|(1<<j)] %= MOD
    
print(dp[-1])