結果

問題 No.2507 Yet Another Subgraph Counting
ユーザー chineristACchineristAC
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
74,496 KB
testcase_01 AC 90 ms
73,600 KB
testcase_02 AC 87 ms
74,112 KB
testcase_03 AC 65 ms
66,048 KB
testcase_04 AC 53 ms
56,960 KB
testcase_05 AC 158 ms
79,616 KB
testcase_06 AC 52 ms
56,320 KB
testcase_07 AC 84 ms
73,216 KB
testcase_08 AC 110 ms
77,608 KB
testcase_09 AC 53 ms
56,704 KB
testcase_10 AC 111 ms
77,440 KB
testcase_11 AC 164 ms
79,744 KB
testcase_12 AC 112 ms
77,568 KB
testcase_13 AC 113 ms
77,440 KB
testcase_14 AC 164 ms
79,616 KB
testcase_15 AC 51 ms
56,064 KB
testcase_16 AC 53 ms
56,704 KB
testcase_17 AC 163 ms
79,744 KB
testcase_18 AC 53 ms
56,448 KB
testcase_19 AC 141 ms
78,592 KB
testcase_20 AC 52 ms
56,832 KB
testcase_21 AC 88 ms
73,600 KB
testcase_22 AC 109 ms
77,696 KB
testcase_23 AC 165 ms
79,744 KB
testcase_24 AC 118 ms
78,080 KB
testcase_25 AC 249 ms
82,304 KB
testcase_26 AC 448 ms
87,296 KB
testcase_27 AC 165 ms
79,616 KB
testcase_28 AC 249 ms
82,048 KB
testcase_29 AC 106 ms
77,696 KB
testcase_30 AC 443 ms
87,296 KB
testcase_31 AC 943 ms
98,304 KB
testcase_32 AC 958 ms
98,048 KB
testcase_33 AC 164 ms
80,000 KB
testcase_34 AC 141 ms
78,848 KB
testcase_35 AC 159 ms
79,744 KB
testcase_36 AC 120 ms
77,952 KB
testcase_37 AC 1,003 ms
98,176 KB
testcase_38 AC 956 ms
98,560 KB
testcase_39 AC 1,000 ms
98,176 KB
testcase_40 AC 1,023 ms
98,432 KB
testcase_41 AC 997 ms
98,304 KB
testcase_42 AC 929 ms
98,304 KB
testcase_43 AC 411 ms
87,296 KB
testcase_44 AC 928 ms
98,176 KB
testcase_45 AC 163 ms
79,744 KB
testcase_46 AC 160 ms
79,616 KB
testcase_47 AC 938 ms
98,176 KB
testcase_48 AC 124 ms
77,952 KB
testcase_49 AC 941 ms
98,304 KB
testcase_50 AC 140 ms
78,720 KB
testcase_51 AC 423 ms
87,296 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