主旋律[清华集训2014 Day1]

响应主旋律的号召，大家决定让这个班级充满爱，现在班级里面有nn个男生。

如果aa爱着bb，那么就相当于aa和bb之间有一条a→ba→b的有向边。如果这nn个点的图是强联通的，那么就认为这个班级是充满爱的。

不幸的是，有一些不好的事情发生了，现在每一条边都可能被摧毁。我作为爱的使者，想知道有多少种摧毁的方式，使得这个班级任然充满爱呢？（说人话就是有多少边的子集删去之后整个图仍然强联通。）

第一行两个数nn和mm，表示班级里的男生数和爱的关系数。

接下来mm行，每行两个数aa和bb，表示男生aa爱着男生bb。同时aa不等于bb。

所有男生从11到nn标号。

同一条边不会出现两遍，但可能出现aa爱着bb，bb也爱着aa的情况，这是两条不同的边。

输出一行一个整数,表示对10^9+7取模后的答案。

SOL：

这是最难的一道题。我一脸蒙蔽。

首先我们发现正面做这道题很难。那么我们求答案的补集。

我们把图缩点后，若其为点数大于1的DAG，那么我们就认为其不合法。

利用容斥原理，DAG图的特征是有至少一个入度为0的点并且这个图不止一个点（这里及以下所说的点都是指求强连通后的 点），就根据这个进行容斥。

我们枚举每一个点集。我们发现其子集对答案的贡献是负的。那么我们枚举每个集合和其子集，每个元素有三种状态，0,1，或是由1枚举子集至0，那么复杂度就是O（3^n）;

#include<bits/stdc++.h>
#define sight(c) ('0'<=c&&c<='9')
#define LL long long
#define mo 1000000007
#define L(x) ((x)&(-(x)))
#define SIZ (1<<16)+7
using namespace std;
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar()) x=x*10+c-48;
}
inline void add(LL &x,LL y){
    x=x+y; if (x>=mo) x%=mo; else if (x<0) (x%=mo)+=mo;
}
int n,m,x,y,in[SIZ],out[SIZ],cnt[SIZ];
LL po[SIZ],num[SIZ],f[SIZ],g[SIZ],M[SIZ],siz,v,ed,sum;
int main (){
    read(n); read(m);
    while (m--) {
        read(x),read(y);
        out[1<<x-1]|=1<<y-1; in[1<<y-1]|=1<<x-1;
    }
    po[0]=1; 
     for (int i=1;i<SIZ;i++) 
      po[i]=(po[i-1]<<1)%mo;
    siz=1<<n; 
    for (int i=1;i<siz;i++) num[i]=num[i-L(i)]+1;
    f[0]=g[0]=1; M[0]=mo-1;
    for (int i=1;i<siz;i++) {
        if (num[i]==1) {
            f[i]=M[i]=g[i]=1; continue;
        }
        x=L(i),v=i-x,ed=0;
        for (int j=0;j<n;j++) if (i&(1<<j)) ed+=num[out[1<<j]&i];
        f[i]=g[i]=po[ed],M[i]=0;
        for (int j=(v-1)&v,now=j|x;~j;j=(j-1)&v,now=j|x)  {
            add(M[i],-f[now]*M[i-now]%mo);
            if (!j) break;
        }
        cnt[i]=0; sum=M[i]*po[cnt[i]]%mo;
        for (int j=(i-1)&i;j;j=(j-1)&i) {
            int La=L(i-j),L=j|La;
            cnt[j]=cnt[L]-num[out[La]&(i-L)]+num[in[La]&j];
            add(sum,M[j]*g[i-j]%mo*po[cnt[j]]%mo);
        }
      add(f[i],-sum);add(M[i],f[i]);
    }
    printf("%lld\n",f[(1<<n)-1]); return 0;
    return 0;
}