3812: 主旋律
题意：一张有向图，求它的生成子图是强连通图的个数。\(n \le 15\)
先说一个比较暴力的做法。
终于知道n个点图的是DAG的生成子图个数怎么求了。
暴力枚举哪些点是一个scc，然后缩点，枚举入度为0的点，容斥原理dp DAG个数
\[d(S) = \sum_{T \subset S, T \neq \varnothing}(-1)^{\mid T\mid-1}2^{w(T,S-T)}d(S-T)
\]
\]
巧妙的做法是直接枚举缩点入度为0的点(即那些scc有哪些点)
\(f(S)\) S的生成子图是强连通的个数
\(g(S)\) S拆成奇数个scc - S拆成偶数个scc. 原因是上面那个DP.
\(h(S)\) 诱导子图S的边数
\[f(S) = 2^{h(S)} - \sum_{T \subset S, T \neq \varnothing} g(T) 2^{w(T, S-T)} 2^{h(S-T)} \\
g(S) = f(S) - \sum_{T \subset S, T \neq \varnothing,T\neq S,p\in T}f(T)g(S-T)
\]
g(S) = f(S) - \sum_{T \subset S, T \neq \varnothing,T\neq S,p\in T}f(T)g(S-T)
\]
注意要把拆成一个单独拿出来，因为更新f用到的g不能是拆成一个！
感觉很巧妙，利用g，相当于把原来不同枚举方案中的DP一块做了！
复杂度\(O(3^n)\)
代码中有一些实现技巧。特别注意怎样固定p在T中
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = (1<<16) + 5, mo = 1e9+7;
inline int read() {
char c=getchar(); int x=0,f=1;
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
int n, m, u, v, f[N], g[N], h[N], one[N], w[N], ins[N], outs[N];
ll mi[N];
int main() {
//freopen("in", "r", stdin);
n = read(); m = read();
for(int i=1; i<=m; i++) {
u = 1 << (read()-1); v = 1 << (read()-1);
outs[u] |= v; ins[v] |= u;
}
mi[0] = 1;
for(int i=1; i<=m; i++) mi[i] = mi[i-1] * 2 %mo;
for(int s = 1; s < 1<<n; s++) one[s] = 1 + one[s ^ (s & -s)];
for(int s = 1; s < 1<<n; s++) {
int p = s & -s, ns = s ^ p;
for(int t = ns; t; t = (t-1) & ns)
g[s] = (g[s] - (ll) f[s ^ t] * g[t]) %mo;
h[s] = h[ns] + one[ins[p] & ns] + one[outs[p] & ns];
f[s] = mi[h[s]];
for(int t = s; t; t = (t-1) & s) {
int p = (s^t) & -(s^t);
if(t == s) w[t] = 0;
else w[t] = w[t ^ p] - one[outs[p] & (s^t)] + one[ins[p] & t];
f[s] = (f[s] - (ll) g[t] * mi[w[t] + h[s^t]]) %mo;
}
if(f[s] < 0) f[s] += mo;
g[s] = (g[s] + f[s]) %mo;
}
printf("%d", f[(1<<n) - 1]);
}