Submission #31278283

Source Code Expand

# popcount は 2 進数 x の 1 の桁の数を数える自作関数
def popcount(x):
    return bin(x).count("1")

MOD = 10 ** 9 + 7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0] * (1 << n)
# dp[i] = 男性 0, ..., popcount(i) - 1 と女性 i (2 進法) だけで popcount(i) ペア作る場合の数
dp[0] = 1
for i in range(1 << n):
    p = popcount(i)
    for j in range(n): # 男性 p - 1 と女性 j をペアにする
        if (i >> j) & 1 == 0 or a[p - 1][j] == 0:
            continue
        dp[i] += dp[i - (1 << j)]
    dp[i] %= MOD
print(dp[(1 << n) - 1])

Submission Info

Submission Time
Task O - Matching
User Pro_ktmr
Language PyPy3 (7.3.0)
Score 100
Code Size 623 Byte
Status AC
Exec Time 1300 ms
Memory 90460 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 17
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12
Case Name Status Exec Time Memory
0_00 AC 69 ms 61840 KiB
0_01 AC 50 ms 62020 KiB
0_02 AC 49 ms 61836 KiB
0_03 AC 1194 ms 90068 KiB
1_00 AC 62 ms 61956 KiB
1_01 AC 47 ms 61948 KiB
1_02 AC 1057 ms 90036 KiB
1_03 AC 1103 ms 89984 KiB
1_04 AC 1164 ms 90308 KiB
1_05 AC 1187 ms 90460 KiB
1_06 AC 1212 ms 90216 KiB
1_07 AC 1300 ms 90200 KiB
1_08 AC 1254 ms 90144 KiB
1_09 AC 1211 ms 90372 KiB
1_10 AC 1251 ms 90348 KiB
1_11 AC 1181 ms 90324 KiB
1_12 AC 1134 ms 90360 KiB