P11714 [清华集训 2014] 主旋律

· · 题解

发现现有的一些题解讲的不太详细，不会的还是不会，于是这里写了一篇较为详细的题解。

或许更好的阅读体验。

思路：

不同于 DAG 计数的是，强联通不好刻画，且几乎无法转化为求解为子问题，于是我们考虑用总的方案数减去不合法的方案数。

考虑动态规划，定义 dp_S 表示使得 S 点集为强联通的子图数量，那么考虑求出不是强连通的子图数量，那么必然可以划分为若干个 SCC，且这些 SCC 缩点后必然是一个 DAG。

注意到上述性质后，按照 DAG 计数的 trick，我们枚举一个子集 T 表示缩点后入度为 0 的点在原图上的点的并集，即这些点构成了若干组两两无边的 SCC；然后设 f_S 表示将 S 划分为若干组两两无边的 SCC 的方案数。

然后考虑对于一个缩点后的 DAG，设其有 cnt 个入度为 0 的点 a_1, \cdots, a_{cnt}，那么肯定会算重，令集合 A_i 表示使得 a_i 入度为 0 的方案数，我们要算 |A_1 \cup \cdots \cup A_{cnt}|，直接容斥即可，对于钦定某 i 个是 SCC 的容斥系数为 (-1)^{i + 1}。

上面的推导，我们算出来的容斥系数是和我们划分出来的 SCC 的个数有关，例如对于点集 |T| 来说，若划分为了 i 个 SCC，则其容斥系数是 (-1)^{i + 1} 而不是和 T 相关的；所以不能直接使用 f_T 来更新转移。

考虑重新修改定义，令 g_T 表示划分为奇数个 SCC 的方案数减去划分为偶数个 SCC 的方案数，那么 g_T 就已经包含了容斥系数了。

然后考虑求若钦定了 T 这个点集为这些入度为 0 的 SCC 的并集后，符合上述钦定的子图数有多少个；首先对于 S - T 内的边，随意删，没有影响，然后对于 u \in T, v \in (S - T) 的有向边 u \to v，也是随意删的。

其它的边都是有限制条件的，例如 u \in (S - T), v \in T 的边 u \to v 必须删掉（不然入度不可能为 0），对于 u, v \in T 内部的边，有内部必须构成若干个两两无边的 SCC 的限制。

然后我们这里定义 E_S 表示 S 的导出子图的边数，E(S, T) 表示 u \in S, v \in T 的有向边 u \to v 的条数，那么我们有状态转移方程：

dp_S = 2^{E_S} - \sum_{T \subset S} g_T 2^{E_{S - T} + E(T, S - T)}

但是这里面我们还少了一点，即钦定 S 这个点集划分为 >1 个 SCC 的方案数，可以看下面 g_S 的转移部分，这里的方案数就是后面的那一坨。

然后来考虑 g_S 的转移，首先有 S 整个划分为一个 SCC，方案数是 dp_S，然后我们枚举一个子集 T，将 T 作为一个新加入的 SCC 进行转移：

g_S = dp_S - \sum_{T \subset S} dp_T g_{S - T}

因为多了 T 这一个 SCC，所以是负号。

看起来很对，但是这样会算重，因为我们考虑若有一个合法的 cnt 个 SCC，那么 T 肯定遍历了这 cnt 个中的任意一个，然后 g_{S - T} 肯定也包含这个方案，故算重了 cnt 次。

于是考虑钦定我们新加入的 SCC 是包含了 x 的，即 x \in S, x\in T，此时对于上面那个合法的方案，包含 x 的 SCC 肯定只有一个，只能被 T 所枚举到一次，故不会算重活算漏。

这里可以令 x = \operatorname{lowbit}(S)，然后我们修改状态转移方程：

g_S = dp_S - \sum_{T \subset S \& \operatorname{lowbit}(S) = \operatorname{lowbit}(T)} dp_T g_{S - T}

此时我们按照上面的转移就是 O(3^nn^2) 的，显然是过不去的，瓶颈在于计算 E(T, S - T)。

考虑令 F_S = E(S, U - S)，其中 U 为全集，那么我们有：

F_T = E(T, U - T) = E(T, S - T) + E(T, U - S) F_S = E(S, U - S) = E(S - T, U - S) + E(T, U - S)

两式子作差，我们有：

E(T, S - T) = F_T - F_S + E(S - T, U - S)

我们令 cnt_{S, i} 表示 E(\{i\}, U - S)，那么：

E(T, S - T) = F_T - F_S + \sum_{i \in (S - T)} cnt_{S, i}

注意到 F_S, cnt_{S, i} 可以 O(m2^n) 预处理，故我们就得到了 O(3^nn) 的做法，可以通过。

link

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) (x & (-x))
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 16, M = 1 << N, MN = 205, mod = 1e9 + 7; 
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, u, v;
int dp[M], g[M], poww[MN], F[M], G[M], cnt[M][N];
vector<int> E[N];
inline void add(int u, int v){
    E[u].push_back(v);
}
inline int calc(int T, int S){
    int sum = F[T] - F[S];
    for(int i = 1; i <= n; ++i)
      if(((S - T) >> (i - 1)) & 1)
        sum += cnt[S][i];
    return sum;
}
bool End;
int main(){
    poww[0] = 1;
    n = read(), m = read();
    for(int i = 1; i <= m; ++i){
        poww[i] = 2ll * poww[i - 1] % mod;
        u = read(), v = read();
        add(u, v);
    }
    for(int S = 1; S < (1 << n); ++ S){
        for(int u = 1; u <= n; ++u){
            if((S >> (u - 1)) & 1){
                for(auto v : E[u]){
                    if((S >> (v - 1)) & 1){
                        ++G[S];
                        continue;
                    }
                    ++cnt[S][u];
                }
                F[S] += cnt[S][u];
            }
        }
        for(int T = (S - 1) & S; T; T = (T - 1) & S){
            if(lowbit(S) != lowbit(T))
              continue;
            g[S] = (g[S] - 1ll * dp[T] * g[S - T] % mod + mod) % mod;
        }
        dp[S] = poww[G[S]];
        for(int T = S; T; T = (T - 1) & S)
          dp[S] = (dp[S] - 1ll * g[T] * poww[G[S - T] + calc(T, S)] % mod + mod) % mod;
        g[S] = (g[S] + dp[S]) % mod;
    }
    write(dp[(1 << n) - 1]);
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}