BZOJ 3812 - 主旋律 | Sengxian's Blog

BZOJ 3812 - 主旋律

#DP #容斥原理

Published on 2016-06-12

题目地址
出处：「陈立杰－计数问题选讲」
百度文库显示 beamer 排版的 PPT 画质很有问题，下载下来就好了。

描述

给你一个 $n(n \le 15)$ 个点的有向简单图，问有多少个边的子集 $E' \subseteq E$ ，使得只保留 $E'$ 中的边的话，整个图还是强连通的。

分析

我讲的可能跟网上的有所不同，但是应该比较易于理解。
思路是：用所有子图数量-非强连通子图的数量。
所有子图是很好求的，为 $2^{m}$ ，问题变为如何求非强连通子图的数量。分析可得如果一个图非强连通，那么将强连通分量缩点之后一定会形成一个 DAG（有向无环图，不必联通）。则我们要求缩点后 DAG 的数量。

考虑状态压缩 DP，设：
$f_s$ 为只保留原图中 $s$ 这些点形成的图的子图中强联通图的数量（也就是题目要求）。
$c_s$ 为只保留原图中 $s$ 这些点，强连通分量缩点后形成 DAG 的数量。
$e_s$ 为只保留原图中 $s$ 这些点形成的图中所有边的数量。

则 $f_s = 2^{h_s} - c_s$ ，那么 $c_s$ 怎么求？根据 DAG 的特性，一定有一些点没有出度，我们枚举有几个没有出度的点，让剩下的点相互随便连边，再让剩下的点向没有出度的点随便连边。这样可以吗？

点不再是单个点，而是强连通分量，不太好枚举。
可能会有重复，因为剩下的点有可能也有一些没有出度的点。

对于第一个问题，我们设 $g_s$ 为将 $s$ 这些点分成若干个强连通分量的数量，我们先看看它和别的量的关系：（为了避免重复统计，找一个点 $u$ 让 $t$ 始终包含 $u$ ）

g_s = f_s + \sum_{t \subset s, u \in t}f_tg_{s - t}

对于第二个问题，我们将状态改为枚举“至少有几个没有出度的点”，容斥着计算。感性的思考一下， $c_s$ 为至少有 1 个点出度为 0 的 DAG 数量 - 至少有 2 个点出度为 0 的 DAG 数量 + 至少有 3 个点出度为 0 的 DAG 数量....

这个形式也是不好求的，因为我们的 $g_s$ 是不包含分成几个强连通分量的，所以无法在打上容斥的符号，考虑修改一下 $g_s$ ：

$g_s$ 为将 $s$ 这些点分成若干个强连通分量的数量，如果有奇数个强连通分量，那么贡献 $-1$ ，否则贡献 $1$ ，这样就能直接乘，不用考虑容斥的符号了。
修改后的 $g_s$ 与 $f_s$ 的关系也很明显：

g_s = f_s - \sum_{t \subset s, u \in t}f_tg_{s - t}

减号的意思是多了一个联通块，对答案的贡献就变成原来的相反数了。 $c_s$ 也可求了。

可以得到：。

这里有个大问题， $g_s, f_s$ 居然是相互需要的！稍加思考可以发现，在 $f_s$ 中枚举 $t$ 的时候，是要忽略掉全图联通的情况的！即 $g_s$ 此时不能加上 $f_s$ 。
所以先算出不加 $f_s$ 的 $g_s$ ，再算 $f_s$ ，最终给 $g_s$ 加上 $f_s$ 。

最后唯一的瓶颈在于求 $e_{s-t, t}$ ， $(s-t) \rightarrow t$ 的边数，这个预处理出 $in_{i, s}$ 只表示考虑 $s$ 中的点，连向 $i$ 的边的数量的和即可。

总的复杂度 $O(3^n)$ ，因为涉及到枚举子集的元素。

代码

暴力求 $e_{s-t, t}$ 版本（不能 A）：

//  Created by Sengxian on 6/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3812 状态压缩 DP + 容斥原理
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 10, modu = 1000000007;
bool G[maxn][maxn];
int n, m, ALL, ecnt[1 << maxn][1 << maxn], powers[maxn * maxn];
ll f[1 << maxn], g[1 << maxn], e_single[1 << maxn];

void solve(int s) {
    int lowbit = s & -s, sw = s ^ lowbit;
    for (int s1 = sw; s1; s1 = (s1 - 1) & sw)
        (g[s] -= f[s - s1] * g[s1] + modu) %= modu;
    f[s] = powers[ecnt[s][s]];
    for (int s1 = s; s1; s1 = (s1 - 1) & s)
        (f[s] -= powers[ecnt[s - s1][s1] + ecnt[s - s1][s - s1]] * g[s1]) %= modu;
    (g[s] += f[s]) %= modu;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    powers[0] = 1;
    for (int i = 1; i < maxn * maxn; ++i) powers[i] = (powers[i - 1] << 1) % modu;
    n = ReadInt(), m = ReadInt();
    ALL = (1 << n) - 1;
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f][t] = true;
    }    
    for (int s = 0; s <= ALL; ++s)
        for (int s1 = 0; s1 <= ALL; ++s1) if (s == s1 || (s & s1) == 0)
            for (int i = 0; i < n; ++i) if ((s >> i) & 1)
                for (int j = 0; j < n; ++j) if ((s1 >> j) & 1)
                    ecnt[s][s1] += G[i][j];
    for (int i = 1; i <= ALL; ++i) solve(i);
    printf("%lld\n", (f[ALL] + modu) % modu);
    return 0;
}

AC:

//  Created by Sengxian on 6/12/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3812 状态压缩 DP + 容斥原理
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 15, modu = 1000000007;
bool G[maxn][maxn];
int n, m, in[maxn][1 << maxn], ALL, powers[maxn * maxn];
ll f[1 << maxn], g[1 << maxn], e_single[1 << maxn];

void solve(int s) {
    int lowbit = s & -s, sw = s ^ lowbit;
    for (int s1 = sw; s1; s1 = (s1 - 1) & sw)
        (g[s] -= f[s - s1] * g[s1] + modu) %= modu;
    for (int i = 0; i < n; ++i) if ((s >> i) & 1) e_single[s] += in[i][s];
    f[s] = powers[e_single[s]];
    for (int s1 = s; s1; s1 = (s1 - 1) & s) {
        int eecnt = 0;
        for (int i = 0; i < n; ++i) if ((s1 >> i) & 1) eecnt += in[i][s - s1];
        (f[s] -= powers[eecnt + e_single[s - s1]] * g[s1]) %= modu;
    }
    (g[s] += f[s]) %= modu;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    powers[0] = 1;
    for (int i = 1; i < maxn * maxn; ++i) powers[i] = (powers[i - 1] << 1) % modu;
    n = ReadInt(), m = ReadInt();
    ALL = (1 << n) - 1;
    for (int i = 0; i < m; ++i) {
        int f = ReadInt() - 1, t = ReadInt() - 1;
        G[f][t] = true;
        for (int s = ALL; s >= 0; --s) if ((s >> f) & 1) in[t][s]++;
    }
    for (int i = 0; i <= ALL; ++i) solve(i);
    printf("%lld\n", (f[ALL] + modu) % modu);
    return 0;
}

BZOJ 1853 - [Scoi2010]幸运数字 HDOJ 4997 - Biconnected