Problem

给出一个有n个点m条边的有向图，问其有多少子图是有向无环图。
1≤n≤17

Step1

比赛时我想到了一个很直观的想法，首先，有向无环图是可以分层的，用二进制状态记录当前已经用过的点和最后一层的点，然后枚举下一层的点的状态，于是可以进行DP，时间复杂度O(4n)

Step2

上面一种方法的局限性在于，它要保留最后一层的点的状态，那么是否可以不用管最后一层的点的状态呢？由于这样直接转移，有的点可能会被计算到下一层中去，这是容斥的模型，对于当前状态S，我们枚举最后一层的点的状态T，如果T中有奇数个点，那么这样的贡献是1，如果是偶数，这样的贡献就是-1

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)using namespace std;int get(){char ch;int s=0;bool bz=0;while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');if (ch=='-')bz=1;else s=ch-'0';while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';if (bz)return -s;return s;
}const int N = 20;
const int L = 131200;
const int mo = 1e+9+7;typedef long long LL;int u[N][L],mi[N*N];
LL f[L];
int n,m;
bool mp[N][N];
bool bz[N];
int w[N],k,now;void dfs(int x,bool sig,int v,int t){if (x>k){if (!t)return;if (sig)f[now|t]=(f[now|t]+LL(f[now])*mi[v]%mo)%mo;else f[now|t]=(f[now|t]+mo-LL(f[now])*mi[v]%mo)%mo;return;}dfs(x+1,sig,v,t);dfs(x+1,sig^1,v+u[w[x]][now],t|mi[w[x]-1]);
}int main(){freopen("obelisk.in","r",stdin);freopen("obelisk.out","w",stdout);n=get();m=get();fo(i,1,m){int x=get(),y=get();mp[x][y]=1;}mi[0]=1;fo(i,1,m)mi[i]=mi[i-1]*2%mo;fo(i,1,n)fo(j,0,mi[n]-1)fo(x,1,n)if ((j&mi[x-1])>0&&mp[x][i])u[i][j]++;memset(f,0,sizeof(f));f[0]=1;fo(i,0,mi[n]-1){k=0;int x=mi[n]-1-i;while(x){w[++k]=floor(log(x&-x)/log(2))+1;x-=x&-x;}now=i;dfs(1,0,0,0);}printf("%d\n",f[mi[n]-1]);fclose(stdin);fclose(stdout);return 0;
}