結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
|
提出日時 | 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 |
ソースコード
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])