正题

题目链接:https://www.luogu.com.cn/problem/AT2390

解题思路

\(n\)个点的\(DAG\)，\(m\)条边可有可无，\(1\)和\(2\)上有石头。求有多少种方案使得先手必胜。

\(1\leq n\leq 15,1\leq m\leq \frac{n(n-1)}{2}\)

解题思路

这个复杂度比较麻烦，要设计一个比较巧妙的\(dp\)。

考虑到题目是问多少种情况\(SG(1)\neq 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\n",(ans-f[MS-1]+P)%P);

	return 0;

}

巴特西

AT2390-[AGC016F]Games on DAG【状压dp,SG函数】

正题

解题思路

解题思路

code

最新文章

热门文章