跳至主要內容

[Hard] P11714 [清华集训 2014] 主旋律

xiezheyuan2025/2/13做题笔记dp状压dp图论计数连通性问题组合计数容斥子集反演约 2102 字大约 11 分钟

简要题意

给定一个 nn 个点 mm 条边的有向图，你需要求出其的边集数，使得断掉边集中的所有边后，整张图强联通。答案对 109+710^9+7 取模。

1≤n≤15,0≤m≤n(n−1)1\leq n\leq 15,0\leq m\leq n(n-1)。

思路

extreme hard 的状压 dp 题，做这道题前最好做一下 P6846 [CEOI 2019] Amusement Park，没做也没有关系。

约定：

  • UU 表示全集 {1,2,⋯ ,n}\{1,2,\cdots,n\}。S−TS-T 表示 TT 在全集 SS 下的补集 ∁ST\complement_S T。
  • p(S)p(S) 表示点集 SS 的导出子图的边数，p(S→T)p(S\to T) 表示满足 u∈S,v∈Tu\in S,v\in T 的有向边 (u,v)(u,v) 的数量。

Part 1

首先设 f(S)f(S) 表示点集为 SS 的强联通图数量，那么答案就是 f(U)f(U)，考虑转移。

首先我们如何刻画强联通题图（以下简称 SCG）这个性质，发现我们趁手的工具非常少，不过刻画强联通分量（以下简称 SCC）的关系工具是存在的，就是缩点。假如我们将整张图缩点后只剩下一个点，那么肯定是 SCG。正难则反，不妨考虑缩点后形成了 ≥2\geq 2 个点的方案数。

缩点后，整张图变成一个 DAG，可以考虑一些对 DAG 计数的方法。

计算 DAG 的数量有一个常见的状态 dp 的方法，就是枚举拓扑序最小的点集，按照拓扑序转移（如果你不熟悉，请尝试完成前面提到的 Amusement Park 一题）。这道题不是计算 DAG，但是可以将一个 SCC 看成一个点，就是计算 DAG 了。

转移？不妨枚举拓扑序最小的所有 SCC 的并集 TT，可以得到一个残缺的转移方程（其中 □(T)\square(T) 表示我们需要补全的部分）：

f(S)=2p(S)−∑T⊆S,T≠∅2p(T→S−T)+p(S−T)⋅□(T)f(S)=2^{p(S)}-\sum_{T\subseteq S,T\neq\varnothing} 2^{p(T\to S-T)+p(S-T)} \cdot \large\square(T)

稍微解释一下，2p(S)2^{p(S)} 即点集为 SS 的子图的方案数。p(T→S−T)p(T\to S-T) 和 p(S−T)p(S-T) 都是不在拓扑序最小的 SCC 的点集的边，无需考虑，所以可以任意选择。

Part 2

我们需要补全上一部分中的 □(T)\square(T)，依据 Amusement Park 一题，很容易写出下面的式子：

□(T)=∑k=1∣T∣(−1)k+1s(T,k)\square(T)=\sum_{k=1}^{|T|}(-1)^{k+1} s(T,k)

其中 s(T,k)s(T,k) 表示将点集 TT 的子图为 kk 的互不连通的 SCC 的方案数。特别地，我们令 T=ST=S 时 k≠1k\neq 1 表示只有一个连通块的方式是禁止的。

简单介绍一下为什么我们这么写。

关注到我们必须保证每次枚举出来的都是恰好拓扑序最小（入度为 00）的点，如果不是则导致计算混乱，不过求出任意一个入度为 00 的子集对应的方案数是容易的。所以不妨引入容斥。但是我不太会容斥，所以可以用一些公式化容斥的东西，比如子集反演。注意下面的推导都是基于 DAG 而不是本题的。

如果设 g(T)g(T) 表示拓扑序最小，f(T)f(T) 表示精确覆盖拓扑序最小。可以写出 g(T)=∑A⊆Tf(T)g(T)=\sum_{A\subseteq T} f(T)，反演得到 f(T)=∑T⊆A(−1)∣A∣−∣T∣g(A)f(T)=\sum_{T\subseteq A}(-1)^{|A|-|T|}g(A)。

故 g(S)=∑T⊆S∑T⊆A(−1)∣A∣−∣T∣g(A)g(S)=\sum_{T\subseteq S}\sum_{T\subseteq A}(-1)^{|A|-|T|}g(A)，稍加变换，得到 g(S)=∑A⊆Sg(A)∑T⊆A(−1)∣A∣−∣T∣g(S)=\sum_{A\subseteq S}g(A) \sum_{T\subseteq A}(-1)^{|A|-|T|}，进一步化简，得到 g(S)=∑A⊆Sg(A)⋅(−1)∣A∣⋅∑k=1∣A∣(∣A∣k)(−1)kg(S)=\sum_{A\subseteq S} g(A)\cdot (-1)^{|A|}\cdot \sum_{k=1}^{|A|}\binom{|A|}{k}(-1)^k。

注意到由于空集没有合适的定义，所以不考虑空集。

根据二项式定理，∑k=1∣A∣(∣A∣k)(−1)k=(−1+1)∣A∣−(∣A∣0)(−1)0=−1\sum_{k=1}^{|A|}\binom{|A|}{k}(-1)^k=(-1+1)^{|A|}-\binom{|A|}{0}(-1)^0=-1，所以最后得到 g(S)=∑A⊆S(−1)∣A∣+1g(S)=\sum_{A\subseteq S} (-1)^{|A|+1}。

本题也需要计算 DAG 结构，所以可以迁移容斥的形式，所以自然要拆分 SCC 数来决定容斥系数 (−1)∣A∣+1(-1)^{|A|+1}。

现在需要求出 s(T,k)s(T,k)，不过这样发现即使可以 O(1)O(1) 求出（况且这也比较困难），大概率也无法通过本题了，所以更加务实的想法是直接求出 □(T)\square(T)。，由于这不再是空缺的，所以赐给它一个字母，用 h(T)h(T) 来表示它。

现在将 h(T)h(T) 回代，得到 f(T)f(T) 的新转移方程：

f(S)=2p(S)−∑T⊆S,T≠∅2p(T→S−T)+p(S−T)⋅h(T)f(S)=2^{p(S)}-\sum_{T\subseteq S,T\neq\varnothing} 2^{p(T\to S-T)+p(S-T)} \cdot h(T)

Part 3

我们需要求出 h(T)h(T)，一种自然的方法是枚举其中一个 SCC，不过这很容易算重。不过有一种更加简单的方法：先确定 TT 中某一个点 uu，然后枚举 uu 的 SCC，可以转移：

−h(S)=∑T⊆S−{u}f(T∪{u})h(S−T∪{u})-h(S)=\sum_{T\subseteq S-\{u\}} f(T\cup\{u\})h(S - T\cup\{u\})

当然这个形式不太美观，可以改一改：

−h(S)=∑T⊆S−{u}h(T)f(S−T)-h(S)=\sum_{T\subseteq S-\{u\}} h(T)f(S-T)

解释一下，TT 是与 uu 在同一个 SCC 的点集（更改后为不在同一个 SCC 的点集），h(S)h(S) 前面有负号，是因为容斥系数的影响，多了一个 SCC 会取反。这个卷积的形式比较好理解，就不讲了。

看起来这个形式很好，不是吗？不过有两点遗留问题：

  • 在 S=TS=T 时，h(T)h(T) 不能取到大小为 11。
  • 在计算 f(S)f(S) 时，如果枚举到了 T=∅T=\varnothing，那么同时也需要用到 f(S)f(S) 的值，导致转移成环。

这两个问题单独出现，都是难以解决的，不过本题中它们一起出现了，T=∅T=\varnothing 就是大小为 11 的情况啊！将式子稍作改写（钦定 h(∅)=1h(\varnothing)=1，这是转移正确性的需要）：

−h(S)=f(S)+∑T⊆S−{u},T≠∅h(T)f(S−T)-h(S)=f(S)+\sum_{T\subseteq S-\{u\},T\neq\varnothing} h(T)f(S-T)

于是只要计算 h(S)h(S) 时先不计算 f(S)f(S) 一项，计算完 f(S)f(S) 后加上即可。

Part 4

如何实现本题？

对于边界，f({u})=h({u})=1f(\{u\})=h(\{u\})=1，然后是时间复杂度：

  • e(S)e(S) 采用 O(n2n)O(n2^n) 或 O(2n)O(2^n) 应该都可以。
  • e(T→S−T)e(T\to S-T) 直接求时间复杂度难以承受，不过发现固定 SS 时是可以利用简单容斥递推计算的（考虑 TT 中的一个点 uu，e(T∪{u}→S−(T∪{u}))e(T\cup\{u\}\to S-(T\cup\{u\})) 和 e(T→S)e(T\to S) 的关系即可），所以优化到了 O(3n)O(3^n)。
  • h(S),f(S)h(S),f(S) 只需要直接枚举子集转移即可，时间复杂度 O(3n)O(3^n)。

于是时间复杂度 O(3n)O(3^n) 可以通过本题，实现并不困难。

代码

#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
#define popcnt(x) __builtin_popcount(x)
using namespace std;

constexpr int mod = 1e9 + 7;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 25, N_ = (1 << 15) + 5, M = N * (N - 1);
int n, m, p[N_], f[N_], h[N_], pw2[M], zak[N_], ind[N], outd[N];
bool g[N][N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i=1,u,v;i<=m;i++){
        cin >> u >> v;
        g[u][v] = 1, ind[v] |= (1 << (u - 1)), outd[u] |= (1 << (v - 1));
    }
    // Step 0: 预处理 2^n
    pw2[0] = 1;
    for(int i=1;i<=m;i++) pw2[i] = Add(pw2[i - 1], pw2[i - 1]);
    // Step 1: 预处理 p(S) 表示点集 S 的导出子图边数
    for(int i=1;i<(1<<n);i++){
        int x = lowbit(i), px = __lg(x) + 1;
        p[i] = p[i ^ x];
        for(int j=1;j<=n;j++){
            if(((i ^ x) >> (j - 1)) & 1) p[i] += g[px][j], p[i] += g[j][px];
        }
    }
    for(int S=1;S<(1<<n);S++){
        if(popcnt(S) == 1){
            f[S] = 1, h[S] = mod - 1;
            continue;
        }
        // Step 2：递推 zak[T] 表示起点在 T，终点在 S-T 的边数
        stack<int> stk;
        for(int T=S;T;T=(T-1)&S) stk.push(T);
        for(;!stk.empty();stk.pop()){
            int T = stk.top(), u = lowbit(T), pu = __lg(u) + 1;
            zak[T] = zak[T ^ u] - popcnt(ind[pu] & (T ^ u)) + popcnt(outd[pu] & (S ^ T));
        }
        // Step 4：递推 h[S] 表示容斥系数
        int x = lowbit(S);
        for(int T=S^x;T;T=(T-1)&(S^x)) h[S] = Sub(h[S], Mul(h[T], f[S ^ T]));
        // Step 3: 递推 f[S] 表示点集为 S 的答案
        f[S] = Add(pw2[p[S]], h[S]);
        for(int T=S;T;T=(T-1)&S){
            if(T == S) continue;
            f[S] = Add(f[S], Mul(h[T], pw2[zak[T] + p[S ^ T]]));
        }
        h[S] = Sub(h[S], f[S]);
    }
    cout << f[(1 << n) - 1] << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。