提出 #17355625

---

ソースコード 拡げる

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))

提出情報

ジャッジ結果