「最初与最后的无名弹幕」

fjy666 · 2022-11-17 13:58:19 · 题解

一道玄妙的状态压缩 dp。
设 F=\{1,2,3,\cdots,n\}， S 为 F 的一个子集。
设 g(S) 为 G 的子图中点集为 S 的图的个数，f(S) 为 G 的联通子图中点集为 S 的图的个数。
则我们所求的答案 \rm ans_{2,3,\cdots,n} 可以表示为

（\mathrm{C}_FS 代表以 F 为全集求 S 的补集）

这可以在 \Theta(n2^n) 内完成。

• 计算 g(S)
  求出满足两个端点 \in S 的边的个数 cnt，则 g(S)=2^{cnt}，可以在 \Theta(2^nm) 内完成、

• 计算 f(S)
  根据容斥原理，f(S)= 所有点集为 S 的子图个数 - 所有点集为 S 的不连通子图个数。
  前面那部分 =g(S)
  后面那部分的话……钦定一个点 v\in S，把不连通子图分成两部分：包含 v 的连通块，不包含 v 的其他部分。
  则可以列出式子

  f(S)=g(S)-\sum_{v\in T\subsetneqq S}f(T)\times g(\mathrm{C}_ST)

  由于枚举所有子集的子集是 \Theta(3^n) 的，所以这部分也是 \Theta(3^n) 的。
  总时间复杂度为 \Theta(3^n+n2^n+m2^n)。