結果

問題 No.2507 Yet Another Subgraph Counting
ユーザー chineristACchineristAC
提出日時 2023-10-13 23:30:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,127 ms / 2,000 ms
コード長 2,662 bytes
コンパイル時間 1,268 ms
コンパイル使用メモリ 86,992 KB
実行使用メモリ 102,644 KB
最終ジャッジ日時 2023-10-13 23:30:52
合計ジャッジ時間 24,553 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 153 ms
81,488 KB
testcase_01 AC 147 ms
81,160 KB
testcase_02 AC 147 ms
81,400 KB
testcase_03 AC 123 ms
79,324 KB
testcase_04 AC 113 ms
74,372 KB
testcase_05 AC 239 ms
83,596 KB
testcase_06 AC 114 ms
74,436 KB
testcase_07 AC 147 ms
81,560 KB
testcase_08 AC 165 ms
81,500 KB
testcase_09 AC 118 ms
74,224 KB
testcase_10 AC 166 ms
81,664 KB
testcase_11 AC 220 ms
83,776 KB
testcase_12 AC 190 ms
81,968 KB
testcase_13 AC 165 ms
81,632 KB
testcase_14 AC 218 ms
83,520 KB
testcase_15 AC 113 ms
74,676 KB
testcase_16 AC 114 ms
74,212 KB
testcase_17 AC 218 ms
83,320 KB
testcase_18 AC 112 ms
74,088 KB
testcase_19 AC 215 ms
82,812 KB
testcase_20 AC 114 ms
74,444 KB
testcase_21 AC 145 ms
81,576 KB
testcase_22 AC 161 ms
81,748 KB
testcase_23 AC 219 ms
83,632 KB
testcase_24 AC 175 ms
82,528 KB
testcase_25 AC 327 ms
86,092 KB
testcase_26 AC 532 ms
91,640 KB
testcase_27 AC 216 ms
83,400 KB
testcase_28 AC 297 ms
86,024 KB
testcase_29 AC 162 ms
81,804 KB
testcase_30 AC 496 ms
91,648 KB
testcase_31 AC 1,024 ms
102,520 KB
testcase_32 AC 1,048 ms
102,172 KB
testcase_33 AC 221 ms
83,620 KB
testcase_34 AC 188 ms
82,844 KB
testcase_35 AC 209 ms
83,800 KB
testcase_36 AC 172 ms
82,492 KB
testcase_37 AC 1,095 ms
102,432 KB
testcase_38 AC 1,014 ms
102,148 KB
testcase_39 AC 1,097 ms
102,480 KB
testcase_40 AC 1,127 ms
102,416 KB
testcase_41 AC 1,099 ms
102,644 KB
testcase_42 AC 1,011 ms
102,280 KB
testcase_43 AC 467 ms
91,320 KB
testcase_44 AC 1,016 ms
102,256 KB
testcase_45 AC 220 ms
83,608 KB
testcase_46 AC 216 ms
83,656 KB
testcase_47 AC 1,038 ms
102,172 KB
testcase_48 AC 176 ms
82,348 KB
testcase_49 AC 1,038 ms
102,444 KB
testcase_50 AC 201 ms
82,704 KB
testcase_51 AC 510 ms
91,404 KB
権限があれば一括ダウンロードができます

ソースコード

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