跳转至

250215 模拟赛 T6 DAG 计数 题解

题目大意

给定一个 \(n\) 个点的有向图，问有多少个边集是无环的。

\(n\le 17\)，\(m\le n\times(n - 1)\)

样例输入

3 6
1 2
2 1
1 3
3 1
2 3
3 2

样例输出

25

题解

这时一类经典的 DAG 计数问题。\(n\le 17\) 可以状压。注意到 DAG 可以分层，因此我们在考虑点集 \(S\) 的答案时，可以枚举 DAG 的最顶层，并向下转移。

考虑一种朴素的 DP：\(f_{i,j}\) 表示点集 \(i\) 中顶层为 \(j\)（入度为 \(0\)）的方案数。通过枚举顶层 \(S_1\)，并使 \(S_1\) 中的每个点向剩下的部分的顶层连至少一条边。这样的时间复杂度为 \(O(4^n)\)，不能通过本题。

我们注意到记录顶层 \(j\) 产生了大量的状态，因此我们尝试去掉这一维度。但是如果直接去掉 \(j\)，会产生重复的贡献。因为这样做去掉了顶层节点入度为 \(0\) 的限制，使得同一个 DAG 的分层方法不唯一。

错误的转移：

\[ f_{S}=\sum_{S_0\subseteq S}{f_{S/S_0}\times E(S/S_0,S_0)} \tag{1} \]

注意到 DAG 的形状只和其边集有关。而这种转移会统计到每种 DAG 的每一种划分方式。我们希望使得同一个 DAG（边集相同）的所有分层方案加起来只产生 \(1\) 的贡献。

我们尝试写出一个上式的等价形式，打散并重排贡献，使得同一个 DAG 不同的划分方式排在一起计算：

\[ \sum_{G_i(V,E_i)} \sum_{k=1}^{n}\sum_{(V_1, V_2,\cdots,V_k)}1 \]

其中 \(G_i(V,E_i)\) 表示所有合法（无环）的 DAG。我们先集中考虑一个 DAG：

\[ \sum_{k=1}^{n}\sum_{(V_1, V_2,\cdots,V_k)}1 \tag{2} \]

其中 \(V_1,V_2,\cdots,V_k\) 依次为最顶层到最底层的分层，因此需要保证 \(V_i\) 内部没有边。

我们希望 \((2)\) 式最终等于 \(1\)，因此可以考虑容斥。这里我们引入一个重要结论：

对于

\[ g(n)=-\sum_{i=1}^{m}{g(n-i)\binom{m}{i}} \tag{3} \]

其中 \(m\) 是任意随机正整数（也就意味着可以不与 \(n\) 有关），而

\[ g(0)=1 \]

则有 \(g(n)=(-1)^n\)。

证明

考虑使用数学归纳法，边界情况显然成立。假设对于全部 \(n<n_0\)，都有 \(g(n)=(-1)^{n}\)。对于 \(g(n_0)\)：

\[ \begin{align*} g(n_0)&=-\sum_{i=1}^{m}{(-1)^{n-i}\binom{m}{i}}\\ &=-(-1)^n\sum_{i=1}^{m}{(-1)^i\binom{m}{i}}\\ &=-(-1)^n(0-1)\\ &=(-1)^n \end{align*} \]

证毕。

我们可以逐步考虑 \(V_1,V_2,V_3\cdots\)，将 \((2)\) 式化为递归的形式：

\[ g(S)=\sum_{V_1\subseteq S}g(S/V_1) \tag{4} \]

其中 \(V_1\) 入度为 \(0\)，内部无边。

我们注意到 \(V_1\) 总是一个极大集合 \((V_1)_{\max}\) 的子集，选择的 \(|V_1|\) 满足 \(|V_1|\le |(V_1)_{\max}|\)。用集合的大小代替集合本身，则方案数形如一种组合数的形式。将 \(|(V_1)_{\max}|\) 作为无关变量 \(m\)，\((4)\) 就拥有了和结论 \((3)\) 极为相似的结构：

\[ g(|S|)=\sum_{|V_1|=1}^{lim}{g(|S|-|V_1|)}\binom{|S|}{|V_1|} \]

但是我们注意到两者相差一个负号。将上式添加负号：

\[ g(|S|)=-\sum_{|V_1|=1}^{lim}{g(|S|-|V_1|)}\binom{|S|}{|V_1|}=(-1)^{|S|} \tag{5} \]

可以将所有负号从递归函数 \(g\) 中提出，还原到 \((2)\) 式中。不难发现负号的数量等于递归的深度，也即分层的数量 \(k\)。因此：

\[ \begin{align*} \sum_{k=1}^{n}\sum_{(V_1, V_2,\cdots,V_k)}&(-1)^k=(-1)^{\sum |V_i|}=(-1)^n\\ \sum_{k=1}^{n}\sum_{(V_1, V_2,\cdots,V_k)}&(-1)^{n+k}=1 \tag{6} \end{align*} \]

结果等于 \(1\)，这正是我们想要的。但由于 \((6)\) 式难以编程计算（需要同时枚举边集 \(E\) 和划分方式 \((V_1,V_2,\cdots)\)），我们还使用 \((1)\) 式类似的结构。这其实很容易处理，根据 \((5)\) 式我们知道：每额外分一层 \(V_i\)，就应该添加一个负号，而负号和连边的方案无关。因此直接在 \((1)\) 式上添加一个负号：

\[ f_{S}=-\sum_{S_0\subseteq S}{f_{S/S_0}\times E(S/S_0,S_0)} \tag{7} \]

再带上剩下的 \((-1)^n\)，则最终答案为

\[ (-1)^nf_{V} \]

\((7)\) 式转移时间复杂度为 \(O(3^n)\)。

到这里 dp 的思路已经完成了。但仍有一个问题：如何 \(O(1)\) 查询 \(E(S_0,S_1)\)。显然如果不考虑空间我们可以 \(O(3^n)\) 预处理出答案，转移时查询即可。但是 \((3^n)\) 开不下数组，需要转换思路。

既然不能预处理，考虑转移的同时 \(O(1)\) 处理 \(E(S/S_0,S_0)\)。然而，\(S/S_0\) 和 \(S_0\) 都在动态变化，无法处理。因此我们需要调整转移顺序，使 \(S/S_0\) 和 \(S_0\) 中的一个固定住。

考虑刷表法。

具体的，记 \(S_1=S/S_0\)。我们考虑对每一个 \(S_1\) 枚举增量 \(S_0\)，并从 \(S_1\) 转移到 \(S_1+S_0\)。这样查询的 \(E(S_1,S_0)\) 中就有一个点集 \(S_1\) 是固定的，使得每遍历到一个新的 \(S_0\)，我们可以通过之前的 \(E(S_1,S_0')\) 用 \(O(1)\) 的时间转移到 \(E(S_1,S_0)\)。显然我们可以取 \(S_0'=S_0\oplus lowbit(S_0)\)，通过预处理求出 \((S_1,lowbit(S_0))\) 产生的边界贡献。

AC 代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<bitset>
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 17;

int n, m;
int a[1 << N], cnt[1 << N], f[1 << N];
int pw2[N * N] = {1};

int tp[1 << N];

signed main() {

    freopen("obelisk.in", "r", stdin);
    freopen("obelisk.out", "w", stdout);

    for(int i = 1; i < (1 << N); i++) {
        cnt[i] = cnt[i ^ (i & -i)] + 1;
    }
    for(int i = 1; i < N * N; i++) {
        pw2[i] = pw2[i - 1] * 2 % MOD;
    }

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        a[1 << v] |= 1 << u;
    }

    f[0] = 1;
    for(int s0 = 0; s0 < (1 << n) - 1; s0++) {
        int s0b = ((1 << n) - 1) ^ s0;
        for(int s1b = (s0b - 1) & s0b; ; s1b = (s1b - 1) & s0b) {
            int s1 = s0b ^ s1b;
            tp[s1] = tp[s1 ^ (s1 & -s1)] + cnt[a[s1 & -s1] & s0];
            f[s0 | s1] = (f[s0 | s1] + f[s0] * pw2[tp[s1]] % MOD * (-1) + MOD) % MOD;
            if(!s1b) break;
        }
        for(int s1b = (s0b - 1) & s0b; ; s1b = (s1b - 1) & s0b) {
            int s1 = ((1 << n) - 1) ^ s1b;
            tp[s1] = 0;
            if(!s1b) break;
        }
    }

    cout << f[(1 << n) - 1] * (n & 1 ? -1 : 1) << endl;

    return 0;
}