JZOJ 6554 赢家

正难则反，首先考虑取补集。

注意到不合法相当于从点 1 出发能走到的点集与从点 2 出发的点集不交。
则考虑枚举这两个集合为 S,T。

设 fS 为在 S 的子图内让 1 能够走到每一个点的方案数，gT 类似。
则除了 S∪T 以外的点，其子图内的边可以随便定向。
但若是从 S∪T 连向外界的边则一定要指向 S∪T。
以及，S,T 之间不能有边相连。
容易发现枚举 S,T 的复杂度是 O(3n) 的。

如何求 fS？
再取补集，不合法的方案则是 1 能走到的点集是 S 的真子集。
考虑枚举这个真子集为 T，则 T 内就是一个子问题，即 fT；T 外的边随意定向；T 与外界相接的边必须指向 T。
此时复杂度依然为 O(3n)。

代码：

#include <cstdio>
#define lowbit(x) ((x) & -(x))
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);
}