【agc016

题目大意

给你一个DAG，边只从编号小的点连到大的点。给你两个棋子一个在1号一个在2号，小A（先手）和小B轮流进行操作：把一个棋子沿着边(x,y)从x移到y。不能操作者输。问原图有多少个子图满足小A必胜。 n<=15

解题思路

首先辨认出是个组合游戏，那么考虑使用SG函数。 我们想要知道有多少种方案sg[1]!=sg[2]。那么我们可以统计sg[1]=sg[2]的然后再减掉。 一种可行的暴力是我把点按sg值分层，然后逐层dp，这样的复杂度稍微有点大。 考虑另一种dp。我们设f[s]表示在考虑了集合s这些点后，保证sg[1]=sg[2]的方案数。（可以没有12，那就相当于12没有边） 我们按照分层的思路，看看能不能在s的底部再垫一层点，这样s的所有点sg值都会变大1。 这是可行的，于是我们子集dp，考虑s的子集t，s-t的点都要向t连至少一条边，s-t的点之间可以随便连，t的点可以和s-t随便连，但是不能连回t。那么这样就可以转移了，第一、三部分方案数可以预处理一个数组，第二部分就是f[s-t]了。 注意枚举子集的时候1和2不能属于不同层。 时间复杂度O(n*3^n)

代码

#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<set> #include<map> using namespace std; #define fo(i,j,k) for(i=j;i<=k;i++) #define fd(i,j,k) for(i=j;i>=k;i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a<b)?a:b) typedef long long ll; const int N=1e6+5,M=2e6+5,mo=1e9+7; int n,m,x,y,ts,s1,s,ns,p,ans,f[1<<16],cnt[16][1<<16],i; ll inc; int tt,b[1000],nxt[1000],fst[1000]; void cr(int x,int y) { tt++; b[tt]=y; nxt[tt]=fst[x]; fst[x]=tt; } int main() { freopen("t6.in","r",stdin); //freopen("t6.out","w",stdout); scanf("%d %d",&n,&m); fo(i,1,m) { scanf("%d %d",&x,&y); cr(x,y); } ts=1<<n;ts--; fo(i,1,n) fo(s,0,ts) for(p=fst[i];p;p=nxt[p]) if ((1<<b[p]-1)&s) cnt[i][s]++; fo(s,0,ts) if ((s&1)==((s>>1)&1)) { f[s]=1; for(ns=(s-1)&s;ns;ns=(ns-1)&s) if ((ns&1)==((ns>>1)&1)) { s1=s-ns; inc=f[s1]; fo(i,1,n) if (s1&(1<<i-1)) (inc*=(1<<cnt[i][ns])-1)%=mo; else if (ns&(1<<i-1)) (inc<<=cnt[i][s1])%=mo; f[s]=(f[s]+inc)%mo; } } ans=1; fo(i,1,m) ans=ans*2%mo; ans-=f[ts]; ans=(ans+mo)%mo; printf("%d",ans); }