noip 2018模拟赛2018.10.29 T2 obelist
又是一道玄学题...
题解:
看到数据范围,显然是状压dp
那么我们来设计一下状态
设dp[i]表示目前选择的点集为i所能获得的无环子图个数
那么如果要求无环,这还是个有向图,所以我们可以将新的子图按拓扑序分层,然后枚举每一层的状态进行转移
所以最浅显的思想就是记录整个点集的状态,同时记录最底层的状态,然后用最底层的状态进行转移,转移时只要求新的层与底层均有连边即可
但是这样做时间复杂度是O(4^n)级别的,显然过不去所有数据
所以我们再考虑进行一些优化:
如果我们不记录最后一层呢?
这样会产生一些重复,所以我们用容斥解决即可:
稍微解释一下重复的产生:由于我们并没有记录哪个状态是末状态,所以我们无法得知相同的状态下最后一层到底是哪个点,但是我们有可能反复地更新了同一个状态,这样做会产生重复
所以我们要进行一些容斥,求出容斥系数即可
然后在更新时枚举子集,边集用2的幂次任选即可
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
#define mode 1000000007
using namespace std;
int dp[(1<<17)+5];
int acc[20][20];
int li[(1<<17)+5];
int p[1005];
int ac[(1<<17)+5];
int kk[(1<<17)+5];
int n,m;
int lowbit(int x)
{
return x&(-x);
}
int main()
{
freopen("obelisk.in","r",stdin);
freopen("obelisk.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x--,y--;
acc[x][y]=1;
}
kk[0]=-1;
for(int i=1;i<(1<<n);i++)
{
if(i&1)
{
kk[i]=kk[i>>1]*(-1);
}else
{
kk[i]=kk[i>>1];
}
}
p[0]=1;
for(int i=1;i<=n*n;i++)
{
p[i]=(p[i-1]<<1)%mode;
}
dp[0]=1;
for(int i=0;i<(1<<n)-1;i++)
{
for(int j=0;j<n;j++)
{
ac[(1<<j)]=0;
}
for(int j=0;j<n;j++)
{
if((1<<j)&i)
{
for(int k=0;k<n;k++)
{
ac[(1<<k)]+=acc[j][k];
}
}
}
li[0]=0;
ll sit=(1<<n)-1-i;
ll j=sit&(sit-1);
while(1)
{
ll t1=sit^j;
ll t2=lowbit(t1);
li[t1]=li[t1^t2]+ac[t2];
dp[t1|i]+=kk[t1]*p[li[t1]]*(ll)dp[i]%mode;
dp[t1|i]%=mode;
if(!j)
{
break;
}
(--j)&=sit;
}
}
printf("%d\n",(dp[(1<<n)-1]%mode+mode)%mode);
return 0;
}