[AGC016 F] Games on DAG

AGC016 F

思路

这个游戏很显然就是一个经典的DAG移子游戏,分为两个子游戏,从$1$开始的和从$2$开始的,所以高橋君获胜当且仅当$1$的SG值和$2$的SG值异或和不为$0$,也就是$1$的SG值和$2$的SG值不相等

直接计算不相等的方案数不好计算,所以我们可以用所有的方案数减去相等的方案数

设$g_S$表示当前已经DP好的点集为$S$的方案数,$f_{i, S}$表示点$i$向点集$S$连的边数

考虑$g_{S}$如何转移。我们可以枚举一个点集$A$,这个点集$A$就是$S$中所有SG值最小的点的集合,令$B=\complement_{S}A$。首先,为了使$1$和$2$的SG值相同,$1$和$2$要么同在$A$,要么同在$B$。$B$中的每个点必须向$A$集合中的至少一个点连边,$A$集合中的点不得有连边,$A$到$B$随便连不连,这样就可以利用$f$对$g$进行转移了

代码

    #include <iostream>
    #include <cstdio>
    #include <vector>
     
    template <typename T> void in(T &_){
        char c=getchar(); _=0; int fl=1;
        while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
        while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
    }
    template <typename T, typename... A> void in(T &_, A &...a){in(_); in(a...);}
     
    #define MOD 1000000007
     
    int N, M, bit[1<<15], f[16][1<<15], g[1<<15];
    bool map[16][16];
     
    int ksm(int x, int y){
        int z=1;
        for(; y; y>>=1, x=1LL*x*x%MOD) if(y&1) z=1LL*z*x%MOD;
        return z;
    }
    int lowbit(int x){return (x&(-x));}
     
    int main(){
        for(int i=0; i<15; i++) bit[1<<i]=i+1;
        in(N, M);
        for(int x, y, i=1; i<=M; i++){
            in(x); in(y);
            map[x][y]=true;
        }
        for(int i=1; i<=N; i++)
            for(int j=0; j<(1<<N); j++)
                f[i][j]=f[i][j-lowbit(j)]+map[i][bit[lowbit(j)]];
        for(int i=0; i<(1<<N); i++){
            g[i]=1;
            for(int j=i&(i-1); j; j=i&(j-1))
                if(((j&1)^((j&2)>>1))==0 && (((i^j)&1)^(((i^j)&2)>>1))==0){
                    int tmp=g[i^j];
                    for(int k=j; k; k-=lowbit(k)) 
                        tmp=1LL*tmp*ksm(2, f[bit[lowbit(k)]][i^j])%MOD;
                    for(int k=i^j; k; k-=lowbit(k))
                        tmp=1LL*tmp*(ksm(2, f[bit[lowbit(k)]][j])-1)%MOD;
                    g[i]=(g[i]+tmp)%MOD;
                }
        }
        printf("%d\n", (ksm(2, M)-g[(1<<N)-1]+MOD)%MOD);
        return 0;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注