BZOJ3812主旋律

/*

这道题其实没有看懂  所以整理一下吧

首先思想转化成所有方案减去不强联通的方案

不强联通的方案相当于很多强联通分量缩点后的dag

转化成子问题, 问很多点的dag方案数

然后枚举作为出度为0的点集 T, 然后S - T和T之间的边是随便连的

但是由于S-T中你不能保证不包含出度为0的点, 所以要容斥

最后得到一个式子

f(S) = \sum{T \belong S T != kongji}  (-1) ^ {|T| - 1} f(S - T) * 2 ^{way(S - T, T)}

ways 函数我们可以通过预先状压一遍求出来

但是这样再转化成原来问题我们需要枚举强联通分量, 显然复杂度不对

然后我们考虑上面那个dp实际上的贡献

我们枚举所有没有出边的强联通分量缩成的点集合T, 假如T中的点组成奇数个强联通分量, 那么对于答案的贡献系数就是1, 否则是-1

用g(S)表示将S分成若干个强联通分量的方案数, 当然这里是要合并进去系数的, F(S)表示S的强联通子图的个数

然后就可以得到G(S) =  F(S) - \sum{T\belong S, u \ T} F(T) g(S - T) (为啥总感觉有一种反演思想)

那么

F(S) = 2 ^ (h(S)) - \sum{T \belong S T != 0} 2 ^ way(T, S - T) + (h(S - T)) g(T)

然后子集dp就好了

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

#include<cmath>

#define ll long long

#define M 15

#define mmp make_pair

using namespace std;

int read() {

    int nm = , f = ;

    char c = getchar();

    for(; !isdigit(c); c = getchar()) if(c == '-') f = -;

    for(; isdigit(c); c = getchar()) nm = nm *  + c - '';

    return nm * f;

}

const int mod = ;

void add(int &x, int y) {

    x += y;

    x -= x >= mod ? mod : ;

    x += x <  ? mod : ;

}

int poww[], f[ << M], g[ << M], h[ << M], p[ << M], in[ << M], out[ << M], bit[ << M], n, m;

int main() {

    n = read(), m = read();

    poww[] = ;

    for(int i = ; i < n * n; i++) poww[i] = (poww[i - ] << ) % mod;

    for(int i = ; i <  << n; i++) bit[i] = bit[i - (i & -i)] + ;

    for(int i = ; i <= m; i++) {

        int x = read(), y = read();

        x =  << (x - ), y =  << (y - );

        out[x] |= y, in[y] |= x;

    }

    for(int s = ; s <  << n; s++) {

        int mad = s & -s, outside = s ^ mad;

        for(int i = outside; i; i = (i - ) & outside)

            add(g[s], -1ll * f[s ^ i] * g[i] % mod);

        h[s] = h[outside] + bit[in[mad] & outside] + bit[out[mad] & outside];

        f[s] = poww[h[s]];

        for(int i = s; i; i = (i - ) & s) {

            if(i != s) {

                int one = (i ^ s) & -(i ^ s);

                p[i] = p[i ^ one] + bit[out[one] & i] - bit[in[one] & (i ^ s)];

            } else p[i] = ;

            add(f[s], -1ll * poww[h[s ^ i] + p[i]] * g[i] % mod);

        }

        add(g[s], f[s]);

    }

    cout << f[( << n) - ] << "\n";

    return ;

}