好像没做过 DAG 计数的题。
首先看到数据范围，考虑状压。
方便起见，记 \(cnt_{S,T}=\sum\limits_{(u,v)\in E}[u\in S \and v \in T]\)。
设 \(f_S\) 表示 \(S\) 为强连通分量的选边方案数，由于正面很难算。
考虑反面：
\[f_S=2^{cnt_{S,S}}-\sum\limits_{\varnothing\subsetneqq T \subseteq S}g_T\times 2^{cnt_{S\backslash T,S}}\\ g_S=\sum\limits_{\varnothing \subsetneqq T \subseteq S}g_{S\backslash T}\times (-f_T) \]初始：
\[f_{\varnothing}=0,g_{\varnothing}=-1 \]这里使用了一个容斥，意思是枚举 \(S\) 的子集 \(T\) 作为出度为 \(0\) 的若干强连通分量的并集。
那么剩下的 \(S\backslash T\) 连出去的边就可以任意选或不选。
但是这样会算重，因为考虑一种选边方案使得出度为 \(0\) 的强连通分量为 \(T_1,T_2,\cdots,T_k\)。
那么这种方案会在任意 \(\varnothing \subsetneqq P\subseteq\{1,2,\cdots k\}\) 的时候被 \(T=\bigcup\limits_{i\in P}T_i\) 计算一次。
由于 \(1=\sum\limits_{\varnothing \subsetneqq P\subseteq\{1,2,\cdots k\}}(-1)^{|P|-1}\)，所以加上这个容斥系数就能做到恰好算到一次。
于是 \(g_{\varnothing}=-1\)，转移时 \(g\) 乘上 \(f\) 时会多乘一个 \(-1\)。
注意转移顺序，应该先转移 \(g\)，再转移 \(f\)，然后等 \(f_S\) 计算好了，再加到 \(g_S\) 上去。
因为计算 \(f_S\) 时所需的 \(g_S\) 是至少两个小集合并起来的，不能算上自己。
另外 \(cnt_{S,S}\) 可以预处理，\(cnt_{S\backslash T,S}\) 可以在每个 \(S\) 的时候枚举 \(T\) 计算一次。
时间复杂度：\(O(3^n\log \log)\)，瓶颈在于计算 popcount。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=15,M=1<<N,E=N*N,mod=1e9+7;
int n,m,U,a[N][N];
int to[N],cnt[M],f[M],g[M],h[M],pw[E];
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m,U=(1<<n)-1;
for(int i=pw[0]=1;i<=m;i++)pw[i]=pw[i-1]*2%mod;
for(int u,v;m--;){
cin>>u>>v,a[--u][--v]=1;
}
for(int u=0;u<n;u++){
for(int v=0;v<n;v++)to[u]|=a[u][v]<<v;
}
for(int S=0;S<=U;S++){
int i=__builtin_ctz(S);
cnt[S]=cnt[S^(S&-S)];
for(int j=0;j<n;j++)if(S>>j&1)cnt[S]+=a[i][j]+a[j][i];
}
g[0]=mod-1;
for(int S=1;S<=U;S++){
for(int T=S;T;--T&=S)if(T&(S&-S)){
g[S]=(g[S]+1ll*g[S^T]*(mod-f[T]))%mod;
}
h[S]=0;
for(int T=S;T;--T&=S){
if(T<S){
int i=__builtin_ctz(S^T);
h[T]=h[T^(1<<i)]+__builtin_popcount(to[i]&S);
}
f[S]=(f[S]+1ll*g[T]*pw[h[T]])%mod;
}
f[S]=(pw[cnt[S]]-f[S]+mod)%mod;
g[S]=(g[S]+f[S])%mod;
}
cout<<f[U];
return 0;
}