我是靠谱客的博主 活力招牌,最近开发中收集的这篇文章主要介绍[agc016F] Games on DAG,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目大意

给定一个n个点m条边DAG,每条有向边(x,y)满足x < y。现在有一个博弈:有两个棋子分别在节点1、2,两人轮流做以下操作:选择一个棋子,由其所在节点的出边移动到另一个节点。不能操作算输。假设两人绝顶,现在问有多少种边的子集满足:保留这些边之后先手必胜。方案数模 109+7

n≤15,没有重边

分析

可以考虑按照sg给图分层。
同时容易发现,两个棋子是两个独立的游戏,为了方便,只需计算两个节点sg值相同的方案数即可,然后总数减不合法。
分层容易想到子集dp。设f[S]表示点集S的导出子图的答案。然后枚举一个非空子集T,表示所有sg=0的点。所有剩余的点为了满足sg>0,必须向T中的点连至少一条边。然后T里面不能有边。接着T的点向剩余的点任意连边。最后乘上剩余的点集里面的答案f[S-T]。理解一下发现这样转移相当于给S-T里的点的sg值整体+1
如何保证节点1、2sg相同?只需保证它们在同一层即可。即S、T中两个状态同时为0或1即可。
一次转移可以通过预处理做到 O(n) ,所以整体复杂度为 O(3nn)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=16,M=1<<15,mo=1e9+7;

typedef long long LL;

int n,m,T,f[M],g[N][M],cnt[N][M],p[M];

bool bz[N][M],ok[M];

int main()
{
    scanf("%d%d",&n,&m); T=1<<n;
    p[0]=1;
    for (int i=1;i<=n;i++) p[i]=p[i-1]*2;
    for (int i=0,x,y;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        bz[x][1<<y-1]=1;
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<T;j++)
        {
            int k=j&-j;
            cnt[i][j]=cnt[i][j^k]+bz[i][k]; g[i][j]=p[cnt[i][j]]-1;
        }
    }
    for (int i=0;i<T;i++) ok[i]=(((1&i)>0)==((2&i)>0));
    f[0]=1;
    for (int i=1;i<T;i++) if (ok[i])
    {
        f[i]=1;
        for (int j=(i-1)&i;j;j=(j-1)&i) if (ok[j])
        {
            int k=i^j,s=f[k];
            for (int x=0;x<n;x++) if (((1<<x)&k)>0) s=(LL)s*g[x+1][j]%mo;
            else if (((1<<x)&j)>0) s=(LL)s*p[cnt[x+1][k]]%mo;
            f[i]=(f[i]+s)%mo;
        }
    }
    int ans=1;
    for (int i=0;i<m;i++) ans=ans*2%mo;
    ans=(ans-f[T-1]+mo)%mo;
    printf("%dn",ans);
    return 0;
}

最后

以上就是活力招牌为你收集整理的[agc016F] Games on DAG的全部内容,希望文章能够帮你解决[agc016F] Games on DAG所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(45)

评论列表共有 0 条评论

立即
投稿
返回
顶部