题解：AT_agc016_f [AGC016F] Games on DAG

· · 题解

首先题目等价于问有多少种图满足 SG_1 = SG_2，总方案减掉即可。

考虑每一次加入一种值，那么这种值显然要和每一种小于它的值的至少一个点连边，并且同一种值之间不能连边。

考虑设状态 f_S 表示已经加入了 S 这个集合的 SG_1=SG_2 的方案数，考虑枚举最后一个加入的集合 T，那么我们需要保证 U/S 里的点都需要向 S 里的点至少一个连边，S 之间不连边且和 U/S 中的点任意连边，乘法原理乘起来即可。

有一个枚举子集的操作，容易做到 O(n 3^n)，感觉不难做到 O(3^n) 但没什么必要。 

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
namespace Manaka_Ao{
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
    char buf[1<<20],*p1=buf,*p2=buf;
    inline int read(){
        int ans=0,w=1;
        char ch=getchar();
        while(ch<48||ch>57){
           if(ch=='-')w=-1;
           ch=getchar();
        }
        while(ch>=48&&ch<=57){
           ans=(ans<<1)+(ans<<3)+ch-48;
           ch=getchar();
        }
        return w*ans;
    }
    const int mod=1000000007;
    const int N=20;
    int n,m;
    struct edge{
        int x,y;
    }ed[N*N];
    int to[N][N];
    int f[(1<<15)+5];
    int c[N][(1<<15)+5];
    signed main(){
        n=read(),m=read();
        int U=(1<<n)-1;
        for(int i=1;i<=m;i++){
            int x=read(),y=read();
            to[x][y]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=0;j<(1<<n);j++){
                for(int k=1;k<=n;k++)if(j&(1<<k-1))c[i][j]+=to[i][k];
            }
        }   
        f[0]=1;
        for(int i=1;i<(1<<n);i++){
            if((i&1)^(i>>1&1))continue;
            for(int j=i;j;j=(j-1)&i){
                if((j&1)^(j>>1&1))continue;
                ll ans=1;
                for(int k=1;k<=n;k++)if((U^i)&(1<<k-1))ans=ans*((1<<c[k][j])-1)%mod;
                for(int k=1;k<=n;k++)if(j&(1<<k-1))ans=ans*(1<<c[k][U^i])%mod;
                f[i]=(f[i]+f[i^j]*ans)%mod;
            }
        }
        ll ans=1;
        for(int i=1;i<=m;i++)ans=ans*2%mod;
        cout<<(ans-f[U]+mod)%mod<<'\n';
        return 0;
    }
}
signed main(){
    Manaka_Ao::main();
    return 0;
}