結果

問題 No.2507 Yet Another Subgraph Counting
コンテスト
ユーザー chineristAC
提出日時 2023-10-13 23:30:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,023 ms / 2,000 ms
コード長 2,662 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 98,560 KB
最終ジャッジ日時 2024-09-15 19:23:31
合計ジャッジ時間 18,435 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 52
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys,random,bisect
from collections import deque,defaultdict
from heapq import heapify,heappop,heappush
from itertools import permutations
from math import gcd

input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())

mod = 998244353

N,M = mi()
edge = [[0]*N for i in range(N)]
edge_S = [0] * N
for i in range(M):
    u,v = mi()
    u,v = u-1,v-1
    edge[u][v] = edge[v][u] = 1
    edge_S[u] ^= 1<<v
    edge_S[v] ^= 1<<u
for i in range(N):
    edge[i][i] = 1

set_sz = [bin(S).count("1") for S in range(1<<N)]
edge_sz = [0 for S in range(1<<N)] 
for S in range(1<<N):
    for i in range(N):
        for j in range(i+1,N):
            if S>>i & 1 and S>>j & 1 and edge[i][j]:
                edge_sz[S] += 1


dp0 = [[[0]*(N) for i in range(1<<N)] for start in range(N)]
"""
dp0[start][S][now]:startから始めてSの頂点をすべてまわるパスのうちnowで終わるパスの数
"""
for s in range(N):
    dp0[s][1<<s][s] = 1
    for S in range(1<<N):
        for now in range(N):
            for nxt in range(N):
                if S>>nxt & 1 == 0 and edge[now][nxt]:
                    dp0[s][S^(1<<nxt)][nxt] += dp0[s][S][now]

hamiltonian = [0 for S in range(1<<N)]
for start in range(N):
    for end in range(N):
        for S in range(1<<N):
            if edge[end][start]:
                hamiltonian[S] += dp0[start][S][end]
for S in range(1,1<<N):
    n = 0
    for i in range(N):
        if S >> i & 1:
            n += 1
    hamiltonian[S] //= n
    if n!=1:
        hamiltonian[S] //= 2


dp1 = [[0]*(N+1) for i in range(1<<N)]
"""
dp1[S][n]:S内の頂点で連結グラフを作る際、サイクルを縮約するとn頂点になるようなグラフの数
dp1[S][1] = (S内のハミルトン閉路の数)
"""
for S in range(1,1<<N):
    dp1[S][1] = hamiltonian[S]
    if set_sz[S] == 2:
        dp1[S][1] = 0
    for n in range(2,set_sz[S]+1):
        """
        cutを選ぶ
        """

        tmp = (S-1) & S
        while tmp!=0:
            x,y = tmp,S^tmp
            if x < y:
                for i in range(1,n):
                    dp1[S][n] += dp1[x][i] * dp1[y][n-i] * (edge_sz[S]-edge_sz[x]-edge_sz[y])
            tmp = (tmp-1) & S
        
        """
        同じグラフが数えられる回数->cutの選び方はn-1通り->(n-1)で割る
        """
        dp1[S][n] //= (n-1)

dp2 = [sum(dp1[S]) for S in range(1<<N)]

#print(dp1)

dp3 = [0 for S in range(1<<N)]
dp3[0] = 1
for S in range(1,1<<N):
    tmp = S
    lsb = S & (-S)
    while tmp:
        if tmp & lsb:
            dp3[S] += dp3[S^tmp] * dp2[tmp]
        tmp = (tmp-1) & S

print(dp3[-1])
0