求助求助
查看原帖
求助求助
224358
清平乐楼主2020/8/31 20:36

思路基本是按照第二篇题解走的,代码实现也基本是仿的第二篇题解,但#8WA了,输出了0

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,mod=1e9+7;
int n,m,k,res=1;
bool visit[N];
int head[N],in[N],f[N][2],g[N][2][2],val[2];
vector<int> a[N],b[N],c;
struct edge{int v,next;}e[N<<1];

inline void add(int u,int v)
{
	e[++k]=(edge){v,head[u]};
	head[u]=k;
	e[++k]=(edge){u,head[v]};
	head[v]=k;
	++in[v],++in[u];
}

void DFS(int u)
{
	visit[u]=true;
	c.push_back(u);
	for(register int i=head[u];i;i=e[i].next)
		if(!visit[e[i].v]) DFS(e[i].v);
}

inline void dp(int l1,int r1,int l2,int r2)
{
	int t=c.size();
	for(register int i=0;i<=t;++i)
		for(register int j=0;j<2;++j)
			for(register int k=0;k<2;++k)
				g[i][j][k]=0;
	for(register int i=l1;i<=r1;++i)
		g[0][0][i]=1;
	if(!a[c[0]][1]||(abs(a[c[0]][1])!=abs(a[c[1]][0])&&abs(a[c[0]][1])!=abs(a[c[1]][1]))) swap(a[c[0]][1],a[c[0]][0]);
	for(register int i=1;i<t;++i)
		if(abs(a[c[i]][0])!=abs(a[c[i-1]][1])) swap(a[c[i]][0],a[c[i]][1]);
	for(register int i=1;i<=t;++i)
		for(register int j=0;j<2;++j)
			for(register int k=0;k<2;++k)
				for(register int l=0;l<2;++l)
					g[i][((a[c[i-1]][0]<0)^j|(a[c[i-1]][1]<0)^k)^l][k]+=g[i-1][l][j];
	for(register int i=0;i<2;++i)
		for(register int j=l2;j<=r2;++j)
			val[i]+=g[t][i][j];
}

inline void calc(void)
{
	if(c.size()==1)
		if(a[c[0]].size()==1) val[0]=val[1]=1;
		else if(abs(a[c[0]][0])!=abs(a[c[0]][1])) val[0]=1,val[1]=3;
		else if(a[c[0]][0]==a[c[0]][1]) val[0]=val[1]=1;
		else val[0]=0,val[1]=2;
	else
	{
		int root=0;
		for(register int i=0;i<c.size();++i)
			if(in[c[i]]==1) root=c[i];
		val[0]=val[1]=0;
		if(root)
		{
			for(register int i=0;i<c.size();++i)
				visit[c[i]]=0;
			c.clear();
			DFS(root);
			int l1=0,l2=0,r1=1,r2=1;
			if(a[c[0]].size()==1) r1=0,a[c[0]].push_back(0);
			if(a[c.back()].size()==1) r2=0,a[c.back()].push_back(0);
			dp(l1,r1,l2,r2);
		}
		else dp(0,0,0,0),dp(1,1,1,1);
	}
}

int main(void)
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d",&k);
		a[i].resize(k);
		for(register int j=0;j<k;++j)
		{
			scanf("%d",&a[i][j]);
			b[abs(a[i][j])].push_back(i);
		}
	}
	k=0;
	for(register int i=1;i<=m;++i)
		if(b[i].size()==2) add(b[i][0],b[i][1]);
		else if(b[i].empty()) res=res*2ll%mod;
	f[0][0]=1,k=0;
	for(register int i=1;i<=n;++i)
		if(!visit[i]&&++k)
		{
			c.clear();
			DFS(i),calc();
			for(register int j=0;j<2;++j)
				f[k][j]=(1ll*f[k-1][j]*val[0]+1ll*f[k-1][!j]*val[1])%mod;
		}
	printf("%d\n",1ll*res*f[k][1]%mod);
	return 0;
}

调了一天了,眼睛都要瞎了

2020/8/31 20:36
加载中...