CF704C.Black Widow

题目大意

题解

链或环，破环成链

随便dp，注意重边

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
#define add(a,b) a=((a)+(b))%1000000007
#define mod 1000000007
#define ll long long
//#define file
using namespace std;

int a[200001][4],ls[100001],b[100001][2],B[100001],d[100001],D[100001],d2[100001],len,n,m,i,j,k,l,l1,l2,s,S,tp,x,y,tot;
ll f[100001][2][2],ans[2],Ans[2],F[2];
bool bz[100001];

void New(int x,int y,int s1,int s2) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;a[len][2]=s1;a[len][3]=s2;}
void NEW(int x,int y,int s1,int s2) {New(x,y,s1,s2);New(y,x,s2,s1);}

void dfs(int t)
{
	int i;bz[t]=1;
	D[++tot]=t;
	
	for (i=ls[t]; i; i=a[i][1])
	if (!bz[a[i][0]])
	d2[tot]=i,dfs(a[i][0]);
}

int main()
{
	#ifdef file
	freopen("CF704C.in","r",stdin);
	#endif
	
	scanf("%d%d",&m,&n);
	fo(i,1,m)
	{
		scanf("%d%d",&tp,&x);
		if (tp==2) scanf("%d",&y),NEW(abs(x),abs(y),x<0,y<0),++d[abs(x)],++d[abs(y)];
		else b[abs(x)][++B[abs(x)]]=x<0;
	}
	
	ans[0]=1;
	fo(i,1,n)
	if (!d[i])
	{
		Ans[0]=Ans[1]=0;bz[i]=1;
		fo(j,0,1)
		{
			s=0;
			fo(l,1,B[i])
			s^=j^b[i][l];
			
			add(Ans[0],ans[0^s]);
			add(Ans[1],ans[1^s]);
		}
		ans[0]=Ans[0],ans[1]=Ans[1];
	}
	fo(i,1,n)
	if (!bz[i] && d[i]==1)
	{
		Ans[0]=Ans[1]=0;
		tot=0;dfs(i);
		fo(j,0,1)
		{
			fo(k,1,tot) memset(f[D[k]],0,sizeof(f[D[k]]));
			
			f[D[1]][0][0]=f[D[1]][1][0]=0;
			s=0;
			fo(l,1,B[D[1]])
			s^=j^b[D[1]][l];
			f[D[1]][j][s]=1;
			
			fo(k,1,tot-1)
			{
				fo(l1,0,1)
				{
					fo(l2,0,1)
					{
						fo(x,0,1)
						{
							s=l2^((l1^a[d2[k]][2])|(x^a[d2[k]][3]));
							fo(l,1,B[D[k+1]])
							s^=x^b[D[k+1]][l];
							
							add(f[D[k+1]][x][s],f[D[k]][l1][l2]);
						}
					}
				}
			}
			add(Ans[0],ans[0]*(f[D[tot]][0][0]+f[D[tot]][1][0])+ans[1]*(f[D[tot]][0][1]+f[D[tot]][1][1]));
			add(Ans[1],ans[0]*(f[D[tot]][0][1]+f[D[tot]][1][1])+ans[1]*(f[D[tot]][0][0]+f[D[tot]][1][0]));
		}
		ans[0]=Ans[0],ans[1]=Ans[1];
	}
	fo(i,1,n)
	if (!bz[i] && d[i]==2)
	{
		Ans[0]=Ans[1]=0;
		tot=0;dfs(i);
		for (j=ls[D[tot]]; j; j=a[j][1])
		if (a[j][0]==D[1] && (j+1)/2!=(d2[1]+1)/2)
		{d2[tot]=j;break;}
		
		fo(j,0,1)
		{
			fo(k,1,tot) memset(f[D[k]],0,sizeof(f[D[k]]));
			
			f[D[1]][0][0]=f[D[1]][1][0]=0;
			s=0;
			fo(l,1,B[D[1]])
			s^=j^b[D[1]][l];
			f[D[1]][j][s]=1;
			
			fo(k,1,tot-1)
			{
				fo(l1,0,1)
				{
					fo(l2,0,1)
					{
						fo(x,0,1)
						{
							s=l2^((l1^a[d2[k]][2])|(x^a[d2[k]][3]));
							fo(l,1,B[D[k+1]])
							s^=x^b[D[k+1]][l];
							
							add(f[D[k+1]][x][s],f[D[k]][l1][l2]);
						}
					}
				}
			}
			memset(F,0,sizeof(F));
			fo(l1,0,1)
			{
				fo(l2,0,1)
				{
					s=l2^((l1^a[d2[tot]][2])|(j^a[d2[tot]][3]));
					add(F[s],f[D[tot]][l1][l2]);
				}
			}
			add(Ans[0],ans[0]*F[0]+ans[1]*F[1]);
			add(Ans[1],ans[0]*F[1]+ans[1]*F[0]);
		}
		ans[0]=Ans[0],ans[1]=Ans[1];
	}
	printf("%I64d
",ans[1]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}