Submission #3973864

Source Code Expand

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

ALL = 1 << N
S = [0]*ALL
MOD = 10**9 + 7
S[ALL-1] = 1
for k in range(N, 0, -1):
    I = [i for i in range(N) if A[k-1][i]]
    v = (1 << k) - 1
    while v < ALL:
        w = S[v] % MOD
        for i in I:
            if v & (1 << i):
                S[v ^ (1 << i)] += w
        x = v & -v; y = v + x
        v = ((v & ~y) // x >> 1) | y
print(S[0] % MOD)

Submission Info

Submission Time
Task O - Matching
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 447 Byte
Status AC
Exec Time 947 ms
Memory 57836 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 174 ms 38256 KiB
0_01 AC 178 ms 38256 KiB
0_02 AC 174 ms 38256 KiB
0_03 AC 597 ms 57196 KiB
1_00 AC 178 ms 38256 KiB
1_01 AC 174 ms 38256 KiB
1_02 AC 295 ms 56684 KiB
1_03 AC 341 ms 57836 KiB
1_04 AC 448 ms 57068 KiB
1_05 AC 494 ms 56940 KiB
1_06 AC 556 ms 57068 KiB
1_07 AC 534 ms 57068 KiB
1_08 AC 694 ms 57068 KiB
1_09 AC 670 ms 57068 KiB
1_10 AC 760 ms 57068 KiB
1_11 AC 947 ms 57324 KiB
1_12 AC 897 ms 57196 KiB