思路基本是按照第二篇题解走的,代码实现也基本是仿的第二篇题解,但#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;
}
调了一天了,眼睛都要瞎了