响应主旋律的号召，大家决定让这个班级充满爱，现在班级里面有 $n$ 个女生。
如果 $a$ 爱着 $b$，那么就相当于 $a$ 和 $b$ 之间有一条 $a \to b$ 的有向边。如果这 $n$ 个点的图是强联通的，那么就认为这个班级是充满爱的。
不幸的是，有一些不好的事情发生了，现在每一条边都可能被摧毁。我作为爱的使者，想知道有多少种摧毁的方式，使得这个班级任然充满爱呢？(说人话就是有多少边的子集删去之后整个图仍然强联通)
第一行包含两个非负整数 $n, m$ ($1 \leq n \leq 15; 0 \leq m \leq n(n-1)$)，表示班级里的女生数和爱的关系数。
接下来 $m$ 行，每行包含两个正整数 $a, b$，表示女生 $a$ 爱着女生 $b$。同时 $a$ 不等于 $b$。
所有女生从 $1$ 到 $n$ 标号。
同一条边不会出现两遍，但可能出现 $a$ 爱着 $b$，$b$ 也爱着 $a$ 的情况，这是两条不同的边。
输出一行一个整数，表示对 $10^9 + 7$ 取模后的答案。
注意到数据规模很小，于是采用状态压缩 DP。
记 $f_S$ 表示集合为 $S$ 的点组成的强连通图 (SCG) 的数量，那么答案就是 $f_U$。边界为 $|S| = 1$ 时 $f_S = 1$。
我们考虑取补计算，即从所有图中减去不是 SCG 的数量，得到的就是答案。
我们记 $e(S)$ 表示原图以 $S$ 导出的子图中一共有多少条边，这个很容易求得。
对于一个非 SCG，缩点后一定有入度为 $0$ 的节点 (反证即可)，因此我们只需枚举 (缩点后) 哪些节点入度为 $0$。注意到除了枚举的节点外，其它节点的入度也可能是 $0$，因此可以采用容斥原理枚举入度为 $0$ 的节点个数。
注意到缩点后的节点其实对应原图中的一个点集，因此这样 DP 复杂度是错的，转移方程太长就不写了。
考虑优化这个 DP。我们换一种方式，考虑枚举入度为 $0$ 的节点对应原图的那个点集 $T$，先不考虑里面有多少个点。如果设 $g_{k, S}$ 表示将点集 $S$ 分成 $k$ 个 SCC 的方案数，则 DP 方程如下：
$$ f_S = 2^{e(S)} + \sum_{T \subseteq S} \sum_{k=1}^{|T|} (-1)^k \cdot g_{k, T} \cdot 2^{e(T, S \setminus T) + e(S \setminus T)} $$
其中 $e(A, B)$ 代表起点在 $A$，终点在 $B$ 的边数，也很容易求得。且当 $T = S$ 时 $k \neq 1$。
注意到后面部分 $2^{e(T, S \setminus T) + e(S \setminus T)}$ 与 $k$ 无关，因此可以提到外面。因此对一个图，我们需要求的就是一个容斥系数，及下列表达式的值：
$$ u_S = \sum_{k=1}^{|S|} (-1)^k \cdot g_{k, S} $$
(如果求出了 $u_S$，那么 $f_S$ 就变成了 $$ f_S = 2^{e(S)} + \sum_{T \subseteq S} u_T \cdot 2^{e(T, S \setminus T) + e(S \setminus T)} $$，可以在 $O \left( 3^n \right)$ 时间内得到解决)
考虑集合 $S$ 所对应的 $u_S$，首先特判 $k = 1$ 的情况 (即只有一个 SCC)，此时的系数为 $-f_S$。如果 $k > 1$，根据套路，我们枚举其中一个节点 $v \in S$ (代码实现中可以令 $v = \mathrm{lowbit}(S)$)。
设 $C$ 为包含 $v$ 的强连通分量，那么考虑集合 $S \setminus C$，如果它里面有 $k$ 个 SCC，对应过来 $S$ 里面就有 $k+1$ 个连通分量，也就是说，需要变号。而 $C$ 里面的点单独成为一个 SCC，因此转移方程马上就出来了：
$$ u_S = - f_S - \sum_{C' \subseteq S \setminus \{v\}} u_{C'} \cdot f_{S \setminus C'} $$ (注：枚举的 $C'$ 为上面讨论的 $S \setminus C$)
边界为 $|S| = 1$ 时 $u_S = -1$。这样一来，$f$ 和 $u$ 都可以在 $O \left( 3^n \right)$ 的时间内完成，故总时间复杂度 $O \left( 3^n \right)$。
ps：代码中的 sc[S] 为 $f_S$，uc[S] 为 $-u_S$，cross[T] 表示 $e(T, S \setminus T)$。
#include <bits/stdc++.h>
#define N 18
#define N2 34000
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int V, E, _V;
int in[N2], out[N2], pop[N2], cross[N2];
// cross[k]: edge count of k -> (i\k)
ll pw2[N2], sc[N2], uc[N2], e[N2];
// sc[i]: strong-connected, uc[i]: IE-coefficient, e[i]: the number of edges
inline void add(ll &x, const ll y) {x = (x + y >= mod ? x + y - mod : x + y);}
int main(){
int i, j, k, u, v;
scanf("%d%d", &V, &E); _V = (1 << V) - 1;
for(i = 1; i <= E; ++i){
scanf("%d%d", &u, &v); u = 1 << u - 1; v = 1 << v - 1;
out[u] |= v; in[v] |= u;
}
for(*pw2 = i = 1; i <= _V; ++i){
pw2[i] = (pw2[i - 1] << 1) % mod;
pop[i] = pop[i >> 1] + (i & 1);
}
for(i = 1; i <= _V; ++i){
v = i & -i; j = i ^ v;
if(!j) {sc[i] = uc[i] = 1; e[i] = 0; continue;}
e[i] = e[j] + pop[in[v] & i] + pop[out[v] & i];
for(k = j; k; k = k - 1 & j)
add(uc[i], mod - uc[k] * sc[i ^ k] % mod);
add(sc[i] = pw2[e[i]], mod - uc[i]);
for(k = i; k; k = k - 1 & i)
if(k == i) cross[i] = 0;
else{
(u = i ^ k) &= -u;
cross[k] = cross[k | u] - pop[out[u] & (i ^ k)] + pop[in[u] & k];
add(sc[i], mod - uc[k] * pw2[cross[k] + e[i ^ k]] % mod);
}
add(uc[i], sc[i]);
}
printf("%lld\n", sc[_V]);
return 0;
}
计算出入边时，为避免使用 clz 函数，在读入时可以令 out[1 << u] = 1 << v; 等代码。
坑1：要注意上面两个式子看似有循环定义，其实不然。因为转移 $f_S$ 时如果 $T = S$ 则 $k \neq 1$，因此可以先处理 $k > 1$ 时的部分 $u_S$，再转移到 $f_S$，最后再转移回 $u_S$。