概述
题目大意
给定一个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(3n∗n)
#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所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复