Submission #17355625


Source Code Expand

Copy
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998_244_353

@njit((i8, i8[:]), cache=True)
def main(N, AB):
    pow2 = np.ones(1 << 15, np.int64)
    for n in range(1, 1 << 15):
        pow2[n] = pow2[n - 1] + pow2[n - 1]
        if pow2[n] >= MOD:
            pow2[n] -= MOD
    A, B = AB[::2] - 1, AB[1::2] - 1
    G = np.zeros((N, N), np.int64)
    for i in range(len(A)):
        a, b = A[i], B[i]
        G[a, b] = G[b, a] = 1
    dp0 = np.zeros((1 << N), np.int64)  # 集合に対して、その中におさまっている辺の数
    for s in range(1 << N):
        for v in range(N):
            if not s & 1 << v:
                continue
            for w in range(v + 1, N):
                if not s & 1 << w:
                    continue
                dp0[s] += G[v, w]
    dp1 = np.zeros(1 << N, np.int64)  # S をラベル付き二部グラフにする方法
    dp1[0] = 1
    for s in range(1 << N):
        t = s
        while True:
            u = s ^ t
            # (u,t) 辺を数える
            e = 0
            for v in range(N):
                """(t, u) 辺の個数を数える
                if u & 1 << v:
                    e += dp0[t, v]"""
                e = dp0[u + t] - dp0[u] - dp0[t]
            dp1[s] += pow2[e]
            if t == 0:
                break
            t = (t - 1) & s
        dp1[s] %= MOD
    dp2 = np.zeros(1 << N, np.int64)  # S をラベル付き連結二部グラフにする方法
    for s in range(1, 1 << N):
        for v0 in range(N):
            if s & 1 << v0:
                break
        # v0 を含む連結成分が t
        x = dp1[s]
        t = s
        while t:
            t = (t - 1) & s
            if t & 1 << v0:
                u = s ^ t
                x -= dp2[t] * dp1[u] % MOD
        dp2[s] = x % MOD
    ans = dp2[-1]
    if ans & 1:
        ans += MOD
    return ans >> 1

N, M = map(int, readline().split())
AB = np.array(read().split(), np.int64)

print(main(N, AB))

Submission Info

Submission Time
Task F - Lights Out on Connected Graph
User maspy
Language Python (3.8.2)
Score 900
Code Size 2189 Byte
Status
Exec Time 1086 ms
Memory 108288 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
× 3
× 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt 1086 ms 108240 KB
random_02.txt 1077 ms 107520 KB
random_03.txt 1080 ms 108208 KB
random_04.txt 1079 ms 107000 KB
random_05.txt 1081 ms 108248 KB
random_06.txt 1071 ms 107152 KB
random_07.txt 1078 ms 108252 KB
random_08.txt 1073 ms 108288 KB
random_09.txt 1078 ms 107216 KB
random_10.txt 1076 ms 108212 KB
random_11.txt 473 ms 105832 KB
random_12.txt 464 ms 105592 KB
random_13.txt 456 ms 106376 KB
random_14.txt 451 ms 105492 KB
random_15.txt 451 ms 105800 KB
random_16.txt 458 ms 106392 KB
random_17.txt 453 ms 105596 KB
random_18.txt 456 ms 106312 KB
random_19.txt 452 ms 106396 KB
random_20.txt 453 ms 105832 KB
random_21.txt 481 ms 106536 KB
random_22.txt 455 ms 105832 KB
random_23.txt 453 ms 106408 KB
random_24.txt 455 ms 106324 KB
random_25.txt 633 ms 106676 KB
random_26.txt 453 ms 105820 KB
random_27.txt 454 ms 105848 KB
random_28.txt 451 ms 106332 KB
random_29.txt 1061 ms 108196 KB
random_30.txt 472 ms 106284 KB
sample_01.txt 465 ms 105672 KB
sample_02.txt 464 ms 105592 KB
sample_03.txt 1062 ms 107776 KB