結果
問題 | No.2507 Yet Another Subgraph Counting |
ユーザー |
|
提出日時 | 2023-08-21 22:49:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,814 ms / 2,000 ms |
コード長 | 4,575 bytes |
コンパイル時間 | 441 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 125,732 KB |
最終ジャッジ日時 | 2024-09-15 14:15:32 |
合計ジャッジ時間 | 30,057 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 52 |
ソースコード
from typing import List, TupleN_MAX = 13popcount = [0] * (1 << N_MAX)for S in range(1, 1 << N_MAX):popcount[S] = popcount[S & (S - 1)] + 1def addeq_poly(f: List[int], g: List[int]):"""f += g"""for i, gi in enumerate(g):f[i] += gidef subeq_poly(f: List[int], g: List[int]):"""f -= g"""for i, gi in enumerate(g):f[i] -= gidef subset_zeta(f: List[int], n: int):"""Inplace conversion from f to ζf. ζf is defined as follows:(ζf)(S) = Σ[T⊆S] f(T)"""block = 1while block < 1 << n:offset = 0while offset < 1 << n:for p in range(offset, offset + block):f[p + block] += f[p]offset += 2 * blockblock <<= 1def subset_zeta_poly(f: List[List[int]], n: int):"""Inplace conversion from f to ζf. ζf is defined as follows:(ζf)(S) = Σ[T⊆S] f(T)"""block = 1while block < 1 << n:offset = 0while offset < 1 << n:for p in range(offset, offset + block):addeq_poly(f[p + block], f[p])offset += 2 * blockblock <<= 1def subset_mobius_poly(f: List[List[int]], n: int):"""Inplace conversion from f to μf. μf is defined as follows:(μf)(S) = Σ[T⊆S] (-1)^(|S/T|) f(T)"""block = 1while block < 1 << n:offset = 0while offset < 1 << n:for p in range(offset, offset + block):subeq_poly(f[p + block], f[p])offset += 2 * blockblock <<= 1def mul_poly(f: List[int], g: List[int]):"""Returns h = fg mod x^n, where f, g are polynomials with degree n-1 defined as follows:f(x) = Σ_i f[i] x^i,g(x) = Σ_i g[i] x^i."""n = len(f)h = [0] * nfor i in range(n):for j in range(n - i):h[i + j] += f[i] * g[j]return hdef ranked(f: List[int], n: int):"""Add rank"""return [[(i == popcount[S]) * f[S] for i in range(n + 1)] for S in range(1 << n)]def deranked(rf: List[List[int]], n: int):"""Remove rank"""return [rf[S][popcount[S]] for S in range(1 << n)]def exp(f: List[int], n: int):"""Subset exp of Σ[S⊆{0,1,...,n-1}] f(S)"""assert f[0] == 0rf = ranked([1], 0)for i in range(n):rg = ranked(f[1 << i: 1 << (i + 1)], i)subset_zeta_poly(rg, i)for S in range(1 << i):rf[S].append(0)rg[S].insert(0, 1)rh = mul_poly(rf[S], rg[S])rf.append(rh)subset_mobius_poly(rf, n)return deranked(rf, n)def bit_deposit(src: int, mask: int, bitwidth: int):dst = 0j = 0for i in range(bitwidth):if (mask >> i) & 1:dst |= ((src >> j) & 1) << ij += 1return dstdef count_cycles(n: int, edges: List[Tuple[int, int]]):cycle = [0] * (1 << n)adj = [[] for _ in range(n)]for u, v in edges:adj[u].append(v)adj[v].append(u)cycle_dp = [[0] * n for _ in range(1 << n)]for v in range(n):cycle_dp[1 << v][v] = 1for s in range(1, 1 << n):start = 0while not ((s >> start) & 1):start += 1for cur in range(n):if cycle_dp[s][cur] == 0:continuefor nxt in adj[cur]:if start == nxt:cycle[s] += cycle_dp[s][cur]elif start < nxt and not ((s >> nxt) & 1):cycle_dp[s | (1 << nxt)][nxt] += cycle_dp[s][cur]for s in range(1, 1 << n):if popcount[s] == 1:cycle[s] = 1elif popcount[s] == 2:cycle[s] = 0else:cycle[s] //= 2return cyclen, m = map(int, input().split())edges = []for _ in range(m):u, v = map(int, input().split())u -= 1v -= 1edges.append((u, v))# E[S] = # of edges connecting vertices in SE = [0] * (1 << n)for u, v in edges:E[(1 << u) | (1 << v)] += 1subset_zeta(E, n)cycle = count_cycles(n, edges)f = [0] * (1 << n)for C in range(1, 1 << n):# max Ct = C.bit_length() - 1# {0, ..., tX} - CS = ((1 << (t + 1)) - 1) ^ Ck = popcount[S]g = [0] * (1 << k)for A in range(1 << k):T = bit_deposit(A, S, t)g[A] = f[T] * (E[T | C] - E[T] - E[C])for A, hA in enumerate(exp(g, k)):X = bit_deposit(A, S, t) | Cf[X] += cycle[C] * hAprint(exp(f, n)[-1])