对题面就不作评价了……
然后嘛，我们考虑用总的子图个数减去不强联通的个数
对于不强联通的个数，我们考虑枚举缩点后出度为0的点的点集，然后容斥，若缩完有奇数个点就减去，有偶数个点就加上
再用一些奇技淫巧
因为不咋想写所以还是推荐跳到大爷那里看注释把-_-
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 20 #define MAXM 32768 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 int n,m; int mp[MAXM],np[MAXM]; ll f[MAXM],g[MAXM],h[MAXM],w[MAXM]; int c[MAXM]; ll mi[MAXN*MAXN]; int main(){ int i,x,y; scanf("%d%d",&n,&m); mi[0]=1; for(i=1;i<=m;i++){ scanf("%d%d",&x,&y); x--; y--; mp[1<<x]|=1<<y; np[1<<y]|=1<<x; mi[i]=(mi[i-1]<<1)%MOD ; } for(i=1;i<MAXM;i++){ c[i]=c[i^(i&-i)]+1; } int N=1<<n; for(i=1;i<N;i++){ x=i&-i; h[i]=h[i^x]+c[mp[x]&(i^x)]+c[np[x]&(i^x)]; y=i^x; for(x=y;x;x=y&x-1){ (g[i]+=MOD-f[i^x]*g[x]%MOD)%=MOD; } f[i]=mi[h[i]]; for(x=i;x;x=i&x-1){ if(i==x){ w[x]=0; }else{ y=(i^x)&-(i^x); w[x]=w[x^y]-c[mp[y]&(i^x)]+c[np[y]&x]; } (f[i]+=g[x]*mi[h[i^x]+w[x]]%MOD)%=MOD; } (g[i]+=MOD-f[i])%=MOD; } printf("%lld\n",f[N-1]); return 0; } /* 5 15 4 3 4 2 2 5 2 1 1 2 5 1 3 2 4 1 1 4 5 4 3 4 5 3 2 3 1 5 3 1 */