BZOJ3812: 主旋律 状压DP+容斥原理

要想求出强连通图的个数，我们可以用所有可能的情况数（即2的总边数次幂，表示每条边选或不选均可）减去在边的选取情况中整张图可以缩为$\geq{2}$个SCC的方案数。

我们枚举所有点是如何被缩成SCC的，即将所有节点划分为$\geq{2}$个集合的所有方案，对于每种方案，每个集合内需要是一张强连通图，这个方案数可以递归计算；将所有集合的方案数乘在一起（乘法原理），然后再乘以“将每个集合看成一个点，有多少张DAG”的方案数，就得到了这种集合划分方案下的方案数。

于是我们只需解决这个问题：给定一张有向图，问有多少种边的选择方案使得这张图是一个DAG。

考虑状压DP，令$f_{s}$表示只考虑集合$s$内的点DAG的方案数。

每张DAG必定都存在一些点不存在出度，我们枚举$t$，考虑不存在出度的点的集合至少为$t$的方案数$g_{t}$。

那么这种情况显然从集合$s-t$内的点要形成一张DAG，随后从集合$s-t$内的点出发，到集合$t$内的点结束的所有边都可以选或不选。

于是方案数为\[g_t=f_{s-t}2^{edges_{s-t,t}}\]

但是实际上我们令不存在出度的点的集合恰好为$t$的方案数为$h_{t}$，我们要计算的$f_{s}=\sum_{t\subseteq{s}}h_t$。

而我们又知道$h_{t}=g(t)-\sum_{t\subset{t'}}h_{t'}$。

于是利用一些容斥知识可以知道$f_{s}=\sum_{t\subseteq{s}}(-1)^{|t|+1}g_{t}$。

这样的话就能计算DAG个数了。

但是集合划分数为Bell数，其中还要进行状压DP，是不能通过的。

现在我们是枚举所有不同的集合划分情况，对于每种情况我们都要枚举$t$按照容斥计算贡献，不妨将$t$提出，优先枚举$t$，这里的$t$没有经过集合划分，就是原问题中的点的集合，他们缩点之后的每个点（也就是划分的集合）必须都是没有出度的，在这个限制下对于他们的每种缩点方式，方案数（x）都为：只要是从集合$s-t$中的点出发的边均可选或者不选。而$t$中若缩成了奇数个点，根据上边的公式贡献应该为正；反之若缩成了偶数个点贡献为负。于是我们只要算出$t$集中的点缩成奇数个点的方案数减去缩成偶数个点的方案数，再乘以刚才的方案数（x）,就得到了这个$t$的贡献。

容易顺便处理出一个子集内的点划分成奇数个没有出度的点的方案数减去划分成偶数个没有出度的点的方案数。

再通过一些预处理就能做到$O(3^n)$了。

详情看代码。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
 
#define N 15
typedef long long ll;
static const int mod = 1000000007;
int out[N][1 << N], pow[N * N], bit[1 << N], tot[1 << N];
int f[1 << N], g[1 << N], temp[1 << N];
void inc(int &x, int y) {
    if ((x += y) >= mod)
        x -= mod;
}
int main() {
    int n, m;
    cin >> n >> m;
    int i, j, k;
    for (i = 0; i < n; ++i)
        bit[1 << i] = i;
    for (pow[0] = 1, i = 1; i <= m; ++i)
        inc(pow[i] = pow[i - 1], pow[i - 1]);
    int a, b;
    for (i = 1; i <= m; ++i) {
        cin >> a >> b;
        --a, --b;
        ++out[a][1 << b];
    }
    for (i = 0; i < n; ++i) {
        for (j = 0; j < (1 << n); ++j) {
            k = j & -j;
            out[i][j] = out[i][j ^ k] + out[i][k];
        }
    }
    for (i = 0; i < (1 << n); ++i) {
        for (j = 0; j < n; ++j) {
            if ((i >> j) & 1)
                tot[i] += out[j][i];
        }
    }
    int s, t, r, x;
    for (s = 1; s < (1 << n); ++s) {
        if (s == (s & -s)) {
            f[s] = g[s] = 1;
            continue;
        }
        temp[0] = 0;
        f[s] = pow[tot[s]];
        g[s] = 0;
        x = bit[s & -s];
        for (t = (s - 1) & s; t; (--t) &= s) {
            r = s - t;
            temp[r] = temp[r ^ (r & -r)] + out[bit[r & -r]][s];
            inc(f[s], mod - (ll)pow[temp[r]] * g[t] % mod);
            if ((t >> x) & 1)
                inc(g[s], mod - (ll)f[t] * g[r] % mod);
        }
        inc(f[s], mod - g[s]);
        inc(g[s], f[s]);
    }
     
    printf("%d", f[(1 << n) - 1]);
     
    return 0;
}

---我是卧底---