如何阳间地数 2-SAT（详细揭秘）

Miko35 · 2024-12-08 02:30:09 · 个人记录

咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕咕

感谢 @灵梦老师提供的资料，时隔不知道多久这个系列终于有后续了，但是你谷个人博客似乎是没了，防止预览的 padding 是形同虚设了，是该可喜可贺吗。

然后内容挺平凡的，，，如果看完觉得毫无信息量不要喷我

下文只对有标号的简单有向图进行讨论。

_upd (2025.02.04)：当时我要把这当离散 project 交上去，所以写了个不那么神金的版本，现在开放。_

前情提要

这部分我们首先回顾一下怎么数 DAG。传统方法不免在系数层面上操作，实在不够阳间！我们引入一种新的操作叫做 arrow product，直接在 GF 层面把问题给你解决，就很阳间了。

EGF & GGF

下文全部用 z 刻画点数，w 刻画边数。

令 a_n(w) 表示有标号图族 \mathcal{A} 中，n 个顶点的图的 OGF。

定义级数序列 (a_n(w))_{n=0}^{\infty} 的指数生成函数 (Exponential GF) \mathrm A(z,w) 和图论生成函数 (Graphic GF) \mathbf{A}(z,w) 为：

\mathrm A(z,w) = \sum_{n\ge 0} a_n(w)\dfrac{z^n}{n!}\\ \mathbf{A}(z,w) = \sum_{n\ge 0} \dfrac{a_n(w)}{(1+w)^{\binom n2}}\dfrac{z^n}{n!}

二者使用粗体进行区分。令 G(z,w) 表示无向图 EGF，\mathbf{D}(z,w) 表示有向图 GGF，\mathbf{Set}(z,w) 表示没有边的图的 GGF：

\mathrm G(z,w) = \mathbf{D}(z,w) = \sum_{n\ge 0} (1+w)^{\binom n2} \dfrac{z^n}{n!}\\ \mathbf{Set}(z,w) = \sum_{n\ge 0} \dfrac{1}{(1+w)^{\binom n2}} \dfrac{z^n}{n!}

注：英文语境下 graph 特指无向图，而有向图是 digraph，所以 GGF 的名字可能有误导。我们一般用 EGF 数无向图而用 GGF 数有向图，但出于历史原因，我们仍采用这个名字。

组合运算

对于有标号图族 \mathcal{A},\mathcal{B}，其不交并的 EGF、GGF 为 \mathrm A(z,w)+\mathrm B(z,w) 与 \mathbf{A}(z,w)+\mathbf{B}(z,w)；其有标号乘（仅重新分配标号，不连边）的 EGF 为 \mathrm A(z,w)\mathrm B(z,w)。

接下来我们定义 \mathcal{A},\mathcal{B} 的箭积 (arrow product)，其包含：对于所有 a\in \mathcal{A}, b\in \mathcal{B}，将 a,b 重新分配标号，且对每个 a 中顶点，都向 b 中顶点的任一子集连边后，形成的所有新有向图。注意结果可能包含两个相同的有向图，你可以理解为二染色。不难发现其 GGF 就是 \mathbf{A}(z,w)\mathbf{B}(z,w)。

你会发现 EGF 和 GGF 符号化构造没有统一，我们还需要定义指数 Hadamard 积：

\mathrm A(z) = \sum_{n\ge 0} a_n\dfrac{z^n}{n!},\mathrm B(z) = \sum_{n\ge 0} b_n\dfrac{z^n}{n!}\\ \mathrm A(z) \odot_z \mathrm B(z) = \sum_{n\ge 0} a_nb_n\dfrac{z^n}{n!}

因为后面我们只会用到 \odot_z，所以我们直接简写成 \odot。我们可以联系 EGF 与 GGF：

\mathbf{A}(z,w) = \mathrm A(z,w) \odot \mathbf{Set}(z,w)\\ \mathrm A(z,w) = \mathbf{A}(z,w) \odot \mathrm G(z,w)\\

注：我一开始觉得这种方式有点丑，但这里原作者阐述了定义算子去完成 EGF 与 GGF 的转化是不完备的原因。此处我们不展开讨论。

DAG 计数

DAG 怎么造出来的？有人就说了，整一个点集表示源点，它向 DAG 随便连边就造出来了。对，对吗？哥们算重了，你要不看看你在数什么，你实际上在数源点被黑白染色的 DAG。

那又有人说了，这题我会啊，引入 u 刻画 DAG 中源点的数目，定义 \mathbf{DAG}(z,w,u) 为标记源点的 DAG 的 GGF，源点被黑白染色的 DAG 不就是 \mathbf{DAG}(z,w,u+1) 吗？所以：

\mathbf{Set}(zu,w)\mathbf{DAG}(z,w,1) = \mathbf{DAG}(z,w,u+1)

再取 u=-1：

\mathbf{DAG}(z,w,1) = \dfrac 1{\mathbf{Set}(-z,w)}

将其回代还可以做带源点数目限制的 DAG 计数。实际上这个跟古法的钦定源点容斥是异曲同工的，但形式简洁太多。

SCC 计数

发现把 SCC 拼成 DAG 就是任意有向图，所以这部分 trivial。

为方便叙述，我们将缩点后的源点的那个连通分量称作 类源连通分量 (source-like SCC)，为汇点的连通分量称作 类汇连通分量 (sink-like SCC)。如果一个 SCC 既类源也类汇，则称其是隔离 (isolated) 的。

简单写写。用 u 刻画类源连通分量并同理定义 \mathbf{D}(z,w,u)，令 \operatorname{SCC}(z,w) 表示 SCC 的 EGF。

\left(\mathbf{Set}(z,w) \odot e^{u \operatorname{SCC}(z,w)}\right) \mathbf D(z,w) = \mathbf{D}(z,w,u+1)\\ \left(\mathbf{Set}(z,w) \odot e^{- \operatorname{SCC}(z,w)}\right) \mathbf D(z,w) = 1\\ \operatorname{SCC}(z,w) = -\ln\left(\mathrm G(z,w) \odot \dfrac{1}{\mathbf D(z,w)}\right)

正事

众所周知啊，虽然判断 2-SAT 问题很容易，但求解 2-SAT 问题解的数量是 NPC 的。~~那咱就说完了~~ 那有人就要问了，不数解的数量还能数啥？jaja，既然是来数图的，我们数的就是有解的 2-SAT 问题数。

首先形式化一下我们的问题：n 个 01 变量，m 条二元关系。一个二元关系指定两不同变量 x,y 必须满足 f(x,y) = 1，其中 f 是某个布尔函数。

根据古法，对于任何的 f 我们都可以建立类似于 x\to y, \bar y \to \bar x 的蕴涵关系。我们把先这样再那样连出的图叫做蕴图 (implication digraph)。我们这么去定义它：

偶数个结点、偶数条边，点有标号 (1,\bar 1,2,\bar2, \ldots, n, \bar n)；
没有重边、自环，也不存在边 (x,\bar x)；
若存在边 (x,y), 则一定存在边 (\bar y, \bar x)。为方便叙述，下面定义同时包含一对 x,\bar x 的 SCC 为矛盾 SCC，否则为普通 SCC。

回顾 2-SAT 的判定，有解当且仅当不存在矛盾 SCC。必要性很好说，充分性我们归纳说明：

两个结点的蕴图显然成立。
蕴图一定存在至少一个类源普通 SCC。
假设对于规模更小的问题这个判定都成立，那么我们任取一个类源普通 SCC，记作 C，那么考虑将 C 中所有标号取反、所有边取反而得到的子图 \bar C，它一定是一个类汇普通 SCC。让 C 全部为假，\bar C 全部为真即归为规模更小的问题。

那也就是说，有解的蕴图只能由普通 SCC 组成。

IGF

令 b_n(w) 表示蕴图族 \mathcal{B} 中，2n 个顶点的图的 OGF。定义级数序列 (b_n(w))_{n=0}^{\infty} 的蕴涵生成函数 (Implication GF) \ddot{\mathbf{B}}(z,w) 为：

\ddot{\mathbf{B}}(z,w) = \sum_{n\ge 0} \dfrac{b_n(w)}{(1+w)^{n(n-1)}}\dfrac{z^n}{2^nn!}

并且定义 \ddot{\mathbf{Set}}(z,w) 表示没有边的图的 IGF：

\ddot{\mathbf{Set}}(z,w) = \sum_{n\ge 0} \dfrac{1}{(1+w)^{n(n-1)}}\dfrac{z^n}{2^nn!}

组合运算

对于有标号蕴图族 \mathcal{A},\mathcal{B}，其不交并的 IGF 为 \ddot{\mathbf{A}}(z,w)+\ddot{\mathbf{B}}(z,w)。

接下来我们定义有标号图族 \mathcal{A} 与有标号蕴图族 \mathcal{B} 的蕴积 (implication product)，其包含以以下方式生成的蕴图：

任取有标号图 A\in \mathcal{A} 与蕴图 B\in \mathcal{B}，不妨 A,B 有 n,2m 个结点；
从 \{1,2,\ldots, n+m\} 重分配标号（仅作数字的重分配，取反标记不变）；
选取 A 的任意一个子集打取反标记，而后将 A 复制一份并全体取反，记作 A'；
对于 A 中每个结点 x，都向 B 中任意子集连边。若连接了 x\to y，则必须同时连接 \bar y\to \bar x（其中 \bar x \in A'）。

那么我们考察它的 IGF，不妨为 \ddot{\mathbf{C}}(z,w)，不用想都知道是 \mathbf{A}(z,w)\cdot \ddot{\mathbf{B}}(z,w)。但是我们还是简要说明一下：第二步 \dbinom{n+m}{n}，第三步 2^n，第四步 (1+w)^{2mn}，第五步注意到 \bar y\in A 所以相当于边已被两两配对，(1+w)^{\binom{n}{2}}。

\begin{aligned} c_n(w)&=\sum_{i=0} \binom{n}{i} 2^i (1+w)^{2i(n-i)+\binom i2} a_i(w)b_{n-i}(w)\\ &=\sum_{i=0} \binom{n}{i} 2^n (1+w)^{n(n-i)+n(i-1)} \dfrac{a_i(w)}{(1+w)^{\binom{i}{2}}} \cdot \dfrac{1}{(1+w)^{(n-i)(n-i-1)}}\dfrac{b_{n-i}(w)}{2^{n-i}}\\ \dfrac{c_n(w)}{n! 2^n (1+w)^{n(n-1)}}&=\sum_{i=0} \dfrac{a_i(w)}{(1+w)^{\binom{i}{2}}i!} \cdot \dfrac{1}{(1+w)^{(n-i)(n-i-1)}}\dfrac{b_{n-i}(w)}{2^{n-i}(n-i)!}\\ [z^n]\ddot{\mathbf{C}}(z,w)&=\sum_{i=0} [z^i]\mathbf{A}(z,w)\cdot [z^{n-i}]\ddot{\mathbf{B}}(z,w)\\ \end{aligned}

那么同样地，对于指数 Hadamard 积：

\ddot{\mathbf{A}}(z,w) = A(z,w) \odot \ddot{\mathbf{Set}}(z,w)\\ A(z,w) = \ddot{\mathbf{A}}(z,w) \odot D(2z,w)\\

怎么数呢？

既然所有 SCC 都是普通 SCC，首先我们有一个初步的想法，像数 DAG 那样将类源 SCC 黑白染色，合并的时候拿一个 SCC 做蕴积。但这样我们就遇到了一个问题：孤立的普通 SCC 显然应该成对产出，但是我们的染色方案只是看到，哦这俩都是类源的，瞎几把染了！所以我们需要多引入一个元来刻画对于孤立 SCC 的处理。

上面是我瞎胡谄的。稍微形式化一点来说。设族 \mathcal F 包含满足以下条件的蕴图：

一开始所有点皆为无色。
对于非隔离类源普通 SCC，挑选出一个子集，并染成黑色；
隔离普通 SCC 是成对出现的。挑选出所有隔离普通 SCC 对的一个子集 T，对于 T 的每个 SCC 对，将其中之一染成黑或白色。

令 \operatorname{SAT}(z,w,u,v) 表示 2-SAT 的 EGF，其中 u 刻画非隔离的类源普通 SCC，v 刻画隔离普通 SCC 对，那么 \mathcal F 的 EGF 是 \operatorname{SAT}(z,w,u+1,2u+2v+1)。

考虑 \mathcal F 的生成方式，无色的点就是原图，先跟一块黑点做蕴积，再拼一块白点。对于白点，我们考虑被染色的那个 SCC，每个点编号是否取反有两种选择，所以 EGF 为 e^{v\operatorname{SCC}(2z,w)}；黑点的 GGF 为 e^{u\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)。所以 \mathcal F 的 EGF 是：

\operatorname{SAT}(z,w,u+1,2u+2v+1) = \left(\left(\left(e^{u\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)\right) \ddot{\mathbf{SAT}}(z,w,1,1)\right)\odot D(2z,w)\right)e^{v\operatorname{SCC}(2z,w)}

然后讨论边界情况，\operatorname{SAT}(z,w,0,v) 代表不存在非隔离的类源普通 SCC 的图，那感情就全是隔离的呗？但是要注意一个细节，类比于二分图计数里边儿左右部点是能交换的，你这一对儿 SCC 也妹说谁先谁后，所以单个 SCC 要除个 2 的系数。答案 e^{v\operatorname{SCC}(2z,w)/2}。

代入 u=-1，

e^{(2v-1)\operatorname{SCC}(2z,w)/2} = \left(\left(\left(e^{-\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)\right) \ddot{\mathbf{SAT}}(z,w,1,1)\right)\odot D(2z,w)\right)e^{v\operatorname{SCC}(2z,w)}\\ e^{-\operatorname{SCC}(2z,w)/2} = \left(\left(e^{-\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)\right) \ddot{\mathbf{SAT}}(z,w,1,1)\right)\odot D(2z,w)\\ e^{-\operatorname{SCC}(2z,w)/2} \odot \ddot{\mathbf{Set}}(z,w)= \left(e^{-\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)\right) \ddot{\mathbf{SAT}}(z,w,1,1)\\ \ddot{\mathbf{SAT}}(z,w,1,1) = \dfrac{e^{-\operatorname{SCC}(2z,w)/2} \odot \ddot{\mathbf{Set}}(z,w)}{e^{-\operatorname{SCC}(z,w)}\odot \mathbf{Set}(z,w)}\\

诶，这不就给你数出来了。注意到：

\operatorname{SCC}(z,w) = -\ln\left(\mathrm G(z,w) \odot \dfrac{1}{\mathbf D(z,w)}\right)\\ \begin{aligned}e^{-\operatorname{SCC}(z,w)} \odot \mathbf{Set}(z,w) &=\mathrm G(z,w) \odot \dfrac{1}{G(z,w)} \odot \mathbf{Set}(z,w)\\ &= \dfrac{1}{G(z,w)} \end{aligned}

代入，我们还得到了它一个更好看的形式：

\begin{aligned} \ddot{\mathbf{SAT}}(z,w) &= \left(e^{-\operatorname{SCC}(2z,w)/2} \odot \ddot{\mathbf{Set}}(z,w)\right)\cdot G(z,w)\\ &= \left(\sqrt{\mathrm G(2z,w) \odot \dfrac{1}{G(2z,w)}} \odot \ddot{\mathbf{Set}}(z,w)\right)\cdot G(z,w) \end{aligned}

注：原论文做的是“对普通/矛盾 SCC 的 GF 确定时的 2-CNF 问题进行计数”的问题，我取了特例之一。思路是一样的，感兴趣自行查阅。