![P11714 [清华集训 2014] 主旋律 题解](https://img2024.cnblogs.com/blog/2914710/202512/2914710-20251210224014313-2136864548.png)
破除心魔了P11714 [清华集训 2014] 主旋律 题解
破除心魔了。
问有多少种删边方案使图强连通。
\(f_s\) 表示 \(s\) 中的点强连通的方案数，如果图不是强连通图，那么它一定可以表示为若干个 SCC 组成的 DAG，考虑由此分割问题。
DAG 计数需要容斥度数为 0 的点，考虑枚举集合 \(t\subseteq s\)，表示 \(t\) 中点组成了若干个缩点之后度数为 0 的 SCC，那么需要把 \(t\) 分割为若干个 SCC，这些 SCC 之间没有边相连，不妨设 \(g_t\) 表示 \(t\) 集合划分为若干没有边相连的 SCC 的方案数。
集合划分枚举最小元所在的 SCC，得到转移：
\[g_t = \sum_{C\subseteq t, \min_{i\in t}i = \min_{j\in C}j}f_tg_{s/t}
\]
考虑 \(f\) 的转移：
\[f_s = 2^{E(s\rightarrow s)}-\sum_{t\subseteq s, t\ne \varnothing} (-1)^{cntscc_t+1}g_t2^{E(t\rightarrow s/t)+E(s/t\rightarrow s/t)}+f_{s}
\]
最后需要加上 \(f_s\) 是因为 \(s = t\) 时，如果只划分了一个 SCC，会减掉 \(f_s\) ，这种情况显然是需要被计算在内的。
这里 \((-1)^{cntscc_t + 1}\) 应该在 \(g_t\) 中被确定，所以不然还需要枚举划分了多少个 SCC，改一下 \(g_t\) 转移：
\[g_t = f_t - \sum_{C\subset t, \min_{i\in t}i = \min_{j\in C}j}f_tg_{s/t}
\]
这样容斥系数被自然算进了 \(g_t\) 里。
这样的式子不能直接转移，因为 \(f_s\) 中似乎用到了 \(g_s\)，而 \(g_s\) 也用到了 \(f_s\)，不过我们进行一些观察之后可以做出以下化简：
\[\begin{aligned}
f_s &= 2^{E(s\rightarrow s)}-\sum_{t\subseteq s, t\ne \varnothing} g_t2^{E(t\rightarrow s/t)+E(s/t\rightarrow s/t)}+f_{s}\\
f_s &= 2^{E(s\rightarrow s)}-\sum_{t\subset s, t\ne \varnothing} g_t2^{E(t\rightarrow s/t)+E(s/t\rightarrow s/t)}-g_s+f_s\\
f_s &= 2^{E(s\rightarrow s)}-\sum_{t\subset s, t\ne \varnothing} g_t2^{E(t\rightarrow s/t)+E(s/t\rightarrow s/t)}-(f_t - \sum_{C\subset t, \min_{i\in t}i = \min_{j\in C}j}f_tg_{s/t})+f_s\\
f_s &= 2^{E(s\rightarrow s)}-\sum_{t\subset s, t\ne \varnothing} g_t2^{E(t\rightarrow s/t)+E(s/t\rightarrow s/t)}+\sum_{C\subset t, \min_{i\in t}i = \min_{j\in C}j}f_tg_{s/t}\\\end{aligned}\\
\]
\(g_s\) 中用到 \(f_s\) 的部分刚好抵消了！所以 \(f_s\) 实际上可以直接计算出来，算完之后再计算 \(g_s\) 即可。
值得注意的是 \(E(a\rightarrow b)\) 看似有 \(4^n\) 个状态，实际上用到的只有 \(3^n + n\) 个，通过一些递推可以在 \(O(3^nn)\) 的时间复杂度内计算所有的 \(E(a\rightarrow b)\)，这是复杂度瓶颈。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 10 + 10, mod = 1e9 + 7;int n, m, f[1 << 15], g[1 << 15], to[1 << 15][N], fr[1 << 15][N], hh[1 << 15], h[1 << 15], pw[N * N];
bool G[N][N];
void dfs(int u, int s) {if(u == n + 1) {for(int t = s; ; t = (t - 1) & s) {h[t] = 0;for(int i = 1; i <= n; i ++) {if(t >> i - 1 & 1) {h[t] = (h[t] + to[s - t][i]);}}if(!t) break;}for(int t = s & (s - 1); t; t = (t - 1) & s) {if((t & -t) == (s & -s)) {g[s] = (g[s] - f[t] * g[s - t]) % mod;}}f[s] = pw[hh[s]];for(int t = s; t; t = (t - 1) & s) {f[s] = (f[s] - g[t] * pw[h[t] + hh[s - t]]) % mod;}g[s] = (g[s] + f[s]) % mod;return ;}dfs(u + 1, s);int ss = s | (1 << u - 1); dfs(u + 1, ss);
} signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m, pw[0] = 1;for(int i = 1; i <= m; i ++) pw[i] = pw[i - 1] * 2 % mod; for(int i = 1; i <= m; i ++) {int x, y; cin >> x >> y;G[x][y] = 1;for(int s = 0; s < (1 << n); s ++) {if(s >> x - 1 & 1) fr[s][y] ++;if(s >> y - 1 & 1) to[s][x] ++;}}for(int s = 1; s < (1 << n); s ++) {int x = __lg(s & -s) + 1;hh[s] = (hh[s - (s & -s)] + fr[s][x] + to[s][x]); }dfs(1, 0);cout << (f[(1 << n) - 1] + mod) % mod << '\n';return 0;
}