AT2390 Games on DAG
题意
\(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob
轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。
思路
发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函数异或值为
0，那么先手胜的情况就是所有情况减去这种情况。
对于所有 SG 函数为 \(v\)
的点，它们必须向 SG 函数小于 \(v\)
的所有点连至少一条边，对大于 \(v\)
的连边没有约束，并且互相不能连边。
所以我们可以枚举当前图的 SG 函数为 0
的点，这样所有其他点都至少向它们连一条边，而它们之间不连边，它们向其他点连边任意。于是对于剩下点的连通子图，我们又可以将所有点的
SG 函数减 1，使它又可以枚举 SG 函数为 0 的点。
于是我们可以 DP。设 \(f_S(1,2\in
S)\) 为对于 \(S\)
所有连通子图满足 1,2 SG 函数相等的方案数。
转移时枚举 \(S\) 的子集 \(T\) 为 SG 函数不为 0 的点，使 \(1,2\in T\) 或 \(1,2\not \in T\)。对于前者情况，\(T\) 对于 \(S\) 的补集为 SG 函数为 0 的点，从 \(f_T\) 转移即可。对于后者情况，1,2 SG 函数为
0，\(T\) 中的边随便连。
DP 前预处理出所有集合被每个点的连边条数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
int w=0,x=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=x*10+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=15,mod=1e9+7;
int n,m,a[maxn][maxn],f[1<<maxn],c[1<<maxn][maxn],pow[maxn*maxn];
inline void work(){
n=read(),m=read();
pow[0]=1;for(int i=1;i<=m;i++) pow[i]=(pow[i-1]<<1)%mod;
for(int x,y,i=1;i<=m;i++) x=read()-1,y=read()-1,a[x][y]=1;
for(int d=1;d<1<<n;d++){
int j=0;
while(~d>>j&1)++j;
for(int x=0;x<n;x++) c[d][x]=c[d^1<<j][x]+a[x][j];
}
for(int d=0;d<1<<n;d++) if((d&3)==3){
f[d]=1;
for(int t=d&(d-1);t;--t&=d) if((t&1)==(t>>1&1)) if(t&1){
int res=1;
for(int i=0;i<n;i++) if(t>>i&1) res=1ll*res*(pow[c[d^t][i]]-1)%mod;
else if(d>>i&1) res=1ll*res*pow[c[t][i]]%mod;
f[d]=(f[d]+1ll*res*f[t])%mod;
}else{
int res=1;
for(int i=0;i<n;i++) if(t>>i&1) res=1ll*res*(pow[c[d^t][i]]-1)%mod*pow[c[t][i]]%mod;
else if(d>>i&1) res=1ll*res*pow[c[t][i]]%mod;
f[d]=(f[d]+res)%mod;
}
}
printf("%d\n",(pow[m]-f[(1<<n)-1]+mod)%mod);
}
}
signed main(){
star::work();
return 0;
}
|
