图论上的状压 DP 计数问题

Vision271 · 2022-09-06 20:39:41 · 个人记录

• 大概就是突然被叫过来肝这个...

• 要总结是吧？我不管，我先把题解放这，后面再整理。

无向图连通块计数

• 题意：求无向图的删边方案数，使得删完边后剩下的图恰好是 k 个极大连通分量。

• 数据范围：n\leqslant 14。

• 乍一看就是个状压。

• 不管如何还是按着想法走。令 dp_{i,j} 表示考虑完前 i 个点，当前有 j 个连通块的方案数。

• 不行，这个状态会有严重的信息丢失。转移的时候开一个新块还好说，如果是要并到已有的块上呢？这可不是斯特林数。

• 考虑逐个连通块考虑。似乎可以从 i 转到 i+siz 来做块。然而还是有问题，这样的连通块，所含的点的编号一定是连续的。

• 换思路。令 dp_{sta,j} 表示用过 sta 中的点，有 j 个连通块。

• 每次暴力一个新连通块塞进去。但是会算重。好啊，没问题啊，钦定所含的最小点的编号为对应块的“编号”，逐编号转移。

• 也就是说，规定每次新选的块一定必须含最小的没有包含的点。

• 从而转移为 dp_{sta,j}=\sum\limits_{substa\subsetneq sta}dp_{substa,j-1}\times f(sta\oplus substa)，其中 f(sta) 为 sta 中点连通的方案数。其实相当于 dp_{sta,1}。

• 考虑怎么求 f：利用减法原理。定义 g(sta) 为 sta 中点任意连边的方案数，显然 g(sta)=2^{edges}。

• 请注意这一步所蕴含的思想：正难则反。事实上，在图上状压计数问题中，我们往往没有较好的办法用 dp_{sta} 的某个或全部子集直接递推出它的结果，于是转而用 g_{sta} 减去不合法方案，这是可做的。

• 则我们有 f(sta)=g(sta)-\sum\limits_{substa\subsetneq sta \And fir\in substa} f(substa)\times g(sta\oplus substa)。

• 即总方案数减去钦定首个点 fir 在某个 substa 中，其余仍然乱放的所有分裂的方案数。

• 显然 dp 是复杂度瓶颈。这个东西的本质是枚举 2^n 的所有子集的所有子集，这个东西的复杂度是 3^n，证明的话...

• 考虑 2^n 的所有子集，容易证明，大小为 siz 的子集有 C(n,siz) 个。对每个子集暴力枚举其子集的复杂度为 O(2^n)，则总复杂度为 \sum\limits_{i=1}^n C(n,i)\times 2^i，考虑将式子展开我们得到 C(n,1)\times 2^1+C(n,2)\times 2^2\times \dots \times C(n,n)\times 2^n。

• 这个式子具有典型的二项式定理特征，考虑取 x=2，则实际上上式就是 (2+1)^n。

• 当然也可以从组合意义来证明，对于 n 位，其在两轮子集选取中的表现一定为 (1,1,1),(1,1,0),(1,0,0) 三种，于是是 3^n。

• p.s.丢人地记一下枚举子集的方法：sub=(sub-1)\And sta。每次将当前最低位改成 0 并退位，然后归约到一个只有这个改成 0 的位为 0，其余均为 1 的子集上，实质上就是当前子集的降序后继子集。

弱化版

• 题意：求无向图的删边方案数，使得删完边后剩下的图中 1 与 k 连通。对每个 k 求解。

• 数据范围：n\leqslant 17。

• 首先直觉为 3^{17}（类似地，上面那个应该有 n\times 3^n 的直觉，因为 14 恰为那个的界）。

• 因为有上面这道题的经验，我们无脑猜一手转化：1 与 k 连通的方案数就是 1 与 k 共连通块的方案数。

• 于是先预处理 f,g。然后暴力枚举 1 所在的极大连通块，块内答案增加，块外贡献系数。

• 预处理 O(3^n)，求解 O(n\times 2^n)。

期望版

• 题意：给定一张 n 个点的无向图，每条边有 p_i 的概率断掉，问期望连通块个数。

• 数据范围：n\leqslant 17。

• 嗯首先这显然是一个 3^n 的复杂度。容易想到一个 dp_{i,sta} 表示构成 i 个连通块用了 sta 的概率，但显然状态数太大了。

• 换一种思路，直接对期望做 DP。

  • 状态设计：P_{sta} 表示 sta 中点连通的概率。E_{sta} 表示考虑了 sta 中的点的期望连通块个数。

  • 初始化：P_{single\ sta}=E_{single\ sta}=1，即孤立点构成一个连通块。

  • 状态转移方程：E_{sta}=\sum\limits_{sub\ that\ highbit(sta)\in sub} P_{sub}\times NP_{sta\oplus sub,sub}\times (1+dp_{sta\oplus sub})。

  • 其中 NP_{sta_1,sta_2} 是 sta_1 与 sta_2 之间没有边的概率。

    • 显然，这一 NP 也可以 DP 出，即 NP_{sta_1,sta_2}=NP_{sub_1,sta_2}\times NP_{sub_2,sta_2}(sub_1\cup sub_2=sta)，O(n\times 2^n)。

    • 不过有一个更简单的办法，即取 UN_{sta} 表示 sta 中没有任何边的概率，invUN_{sta} 为其逆元，然后可以差分。

• 综上，总复杂度 O(3^n)。

• 血的教训：诸如“sta 内的点构成一个极大连通块的概率”的东西是绝对不可求的。

• 这玩意一没法容斥（highbit(sta) 所在的连通块可能不包含于 sta），二没法递推（新增点 lowbit(sta) 可能是该连通块的割点，即依靠它连通了整个块，从而不需要已有部分连通），我是没办法。

有向图删边：DAG

• 这是那个 T2 的前置科技吧...