正题
题目链接:https://www.luogu.com.cn/problem/AT2390
解题思路
(n)个点的(DAG)，(m)条边可有可无，(1)和(2)上有石头。求有多少种方案使得先手必胜。
(1leq nleq 15,1leq mleq frac{n(n-1)}{2})
解题思路
这个复杂度比较麻烦，要设计一个比较巧妙的(dp)。
考虑到题目是问多少种情况(SG(1) eq SG(2))，其实求(SG(1)=SG(2))的方案会更简单些。
设(f_{S})表示目前只考虑了生成子图(S)时(SG(1)=SG(2))的方案数，那么若从(T)转移到(S)时我们可以构造一种方案使得(T)的所有点内的(SG)加一，然后(S/T)的所有点的(SG)为(0)。
也就相当于我们把点按照(SG)大小分成若干层，然后一层一层转移进去。好了现在考虑怎么转移(f_S)，我们枚举它的子集(T)，那么(S/T)就是它的下一层，也就是目前(S/T)内的点(SG=0)。
对于(T)内的每个点，我们需要连接至少一个(S/T)内的点，对于(S/T)内的点，可以随意连接(T)内的点，枚举一下点集统计方案就好了。
时间复杂度(O(3^nn))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const ll N=15,P=1e9+7;
ll n,m,ans,f[1<<N],c[1<<N],e[N];
vector<int>q[N];
signed main()
{
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
ll x,y;
scanf("%lld%lld",&x,&y);
x--;y--;e[x]|=(1<<y);
}
ll MS=(1<<n),o=0;c[0]=1;
for(ll i=1;i<MS;i++)c[i]=c[i-(i&-i)]*2;
for(ll s=0;s<MS;s++){
if((s&1)!=((s>>1)&1))continue;
f[s]=1;
for(ll t=(s-1)&s;t;t=(t-1)&s){
ll buf=f[t];
for(ll i=0;i<n;i++){
if((t>>i)&1)buf=buf*(c[(s^t)&e[i]]-1)%P;
if(((s^t)>>i)&1)buf=buf*c[t&e[i]]%P;
}
(f[s]+=buf)%=P;
}
}
ll ans=1;
while(m)m--,ans=ans*2%P;
printf("%lld
",(ans-f[MS-1]+P)%P);
return 0;
}