【AtCoder Grand Contest 016 F】Games on DAG | Mrsrz's blog

状压 DP，博弈论。

题目大意：

给定一张有向无环图，一开始有两个棋子在 $1$ 和 $2$ 结点上。

两人轮流行动，每次可以选择一个棋子，并走过一条边。不能行动者输。

问这张图有多少张子图，能使先手必胜。

题解：

妙。

先手必胜的条件是 $1$ 和 $2$ 的 sg 值不相等。

我们考虑求 $1$ 和 $2$ 的 sg 值相等的方案数。

考虑状压 DP，令 $f_S$ 表示点集 $S$ 中的元素，满足 $1$ 和 $2$ 的 sg 值相等的方案数。

所以 $S$ 首先一定包含 $1$ 和 $2$。

我们考虑枚举 $S$ 的子集 $U$，表示 sg 值为 $0$ 的部分，其补集 $T$ 为 sg 值不为 $0$ 的部分。

考虑它们之间的连边：

• $U$ 内部不能连边，否则不能保证 sg 值为 $0$。
• $T$ 的每个点必须至少有一条路径到 $U$ 中的一个点，保证是必胜态。
• $U$ 到 $T$ 任意连边。
• $T$ 内部的连边的总数就是 $f_T$。因为 $T$ 中所有点都向 sg 值为 $0$ 的点连边，相当于 $T$ 里每个点的 sg 值整体都加了 $1$。所以是不为 $0$ 的方案。

$U$ 和 $T$ 也要保证 $1$ 和 $2$ 的 sg 值一样，所以要么同时包含 $1$ 和 $2$，要么同时不含。

这样就可得到先手必败的方案数。用总数减去其即可。

时间复杂度 $O(3^nn)$。

Code：

#include<cstdio>
#define popcnt __builtin_popcount
typedef long long LoveLive;
const int N=15,M=32768,md=1e9+7;
int f[M],n,m,e[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        e[u-1]|=1<<(v-1);
    }
    const int C=1<<n;
    f[0]=1;
    for(int S=3;S<C;++S)if((S&1)==(S>>1&1))
    for(int U=S;U;U=(U-1)&S)if((U&1)==(U>>1&1)){//sg=0
        int T=S^U;
        int T_U=1,U_T=1;
        for(int i=0;i<n;++i){
            if(U>>i&1)U_T=U_T*(1LL<<popcnt(e[i]&T))%md;else
            if(T>>i&1)T_U=T_U*((1LL<<popcnt(e[i]&U))-1)%md;
        }
        f[S]=(f[S]+(LoveLive)U_T*T_U%md*f[T])%md;
    }
    int ans=1;
    for(int i=1;i<=m;++i)ans=ans*2%md;
    ans=(ans-f[C-1]+md)%md;
    printf("%d",ans);
    return 0;
}