正难则反，首先考虑取补集。
注意到不合法相当于从点 \(1\) 出发能走到的点集与从点 \(2\) 出发的点集不交。
则考虑枚举这两个集合为 \(S,T\)。
设 \(f_S\) 为在 \(S\) 的子图内让 \(1\) 能够走到每一个点的方案数，\(g_T\) 类似。
则除了 \(S \cup T\) 以外的点，其子图内的边可以随便定向。
但若是从 \(S \cup T\) 连向外界的边则一定要指向 \(S \cup T\)。
以及，\(S,T\) 之间不能有边相连。
容易发现枚举 \(S,T\) 的复杂度是 \(O(3^n)\) 的。
如何求 \(f_S\)？
再取补集，不合法的方案则是 \(1\) 能走到的点集是 \(S\) 的真子集。
考虑枚举这个真子集为 \(T\)，则 \(T\) 内就是一个子问题，即 \(f_T\)；\(T\) 外的边随意定向；\(T\) 与外界相接的边必须指向 \(T\)。
此时复杂度依然为 \(O(3^n)\)。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
const int N = 15;
const int M = 105;
const int mod = 1e9 + 7;
int n,m,full,pw[M + 5];
int e[N + 5][(1 << N) + 5],s[(1 << N) + 5];
int f[(1 << N) + 5],g[(1 << N) + 5],ans;
int main()
{
freopen("winner.in","r",stdin),freopen("winner.out","w",stdout);
scanf("%d%d%*d",&n,&m),pw[0] = 1,full = (1 << n) - 1;
int u,v;
for(register int i = 1;i <= m;++i)
pw[i] = 2LL * pw[i - 1] % mod,scanf("%d%d",&u,&v),++e[u][1 << v - 1],++e[v][1 << u - 1];
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
e[i][j] = e[i][j ^ lowbit(j)] + e[i][lowbit(j)];
for(register int i = 0;i <= full;++i)
for(register int j = 1;(1 << j - 1) < lowbit(i);++j)
s[i | (1 << j - 1)] = s[i] + e[j][i];
for(register int i = 0;i <= full;++i)
if(i & 1)
{
f[i] = pw[s[i]];
for(register int j = i & (i - 1);j;j = (j - 1) & i)
(j & 1) && (f[i] = (f[i] - (long long)f[j] * pw[s[i ^ j]] % mod + mod) % mod);
}
for(register int i = 0;i <= full;++i)
if(i & 2)
{
g[i] = pw[s[i]];
for(register int j = i & (i - 1);j;j = (j - 1) & i)
(j & 2) && (g[i] = (g[i] - (long long)g[j] * pw[s[i ^ j]] % mod + mod) % mod);
}
ans = pw[m];
for(register int i = 0;i <= full;++i)
for(register int S = i,T;T = i ^ S,S;S = (S - 1) & i)
if((S & 1) && (T & 2) && s[S] + s[T] == s[i])
ans = (ans - (long long)f[S] * g[T] % mod * pw[s[full ^ i]] % mod + mod) % mod;
printf("%d\n",ans);
}