提出 #31278376

ソースコード 拡げる

MOD = 10 ** 9 + 7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
popcount = [bin(x).count("1") for x in range(1 << n)]
dp = [[0] * (1 << n) for i in range(n + 1)]
# dp[i][j] = 男性 0, ..., i - 1 と女性 j (2 進法) だけで i ペア作る場合の数
dp[0][0] = 1
for i in range(1, n + 1):
    for j in range(1 << n):
        if popcount[j] != i: # ここで popcount を毎回計算すると計算量が悪化するので前計算しておく
            continue # この continue がないと計算量が悪化する
        for k in range(n): # 男性 i - 1 と女性 k をペアにする
            if (j >> k) & 1 == 0 or a[i - 1][k] == 0:
                continue
            dp[i][j] += dp[i - 1][j - (1 << k)]
        dp[i][j] %= MOD
print(dp[n][(1 << n) - 1])

提出情報

提出日時
問題 O - Matching
ユーザ Pro_ktmr
言語 PyPy3 (7.3.0)
得点 100
コード長 818 Byte
結果 AC
実行時間 1596 ms
メモリ 453164 KiB

ジャッジ結果

セット名 All
得点 / 配点 100 / 100
結果
AC × 17
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
0_00 AC 65 ms 62020 KiB
0_01 AC 48 ms 61980 KiB
0_02 AC 45 ms 62008 KiB
0_03 AC 1555 ms 452960 KiB
1_00 AC 65 ms 62020 KiB
1_01 AC 46 ms 61928 KiB
1_02 AC 1437 ms 453016 KiB
1_03 AC 1476 ms 453112 KiB
1_04 AC 1520 ms 453164 KiB
1_05 AC 1552 ms 453156 KiB
1_06 AC 1548 ms 453056 KiB
1_07 AC 1552 ms 452804 KiB
1_08 AC 1596 ms 453032 KiB
1_09 AC 1595 ms 452920 KiB
1_10 AC 1590 ms 453108 KiB
1_11 AC 1579 ms 453152 KiB
1_12 AC 1579 ms 453140 KiB