Codeforces704C. Black Widow
2024-08-27 23:13:31
n<=1e5个值v，分别由<=1e5的m个变量中的1<=ki<=2个布尔变量xj（或某个变量取反）或起来组成，而所有的v异或起来为1，一个x不会在输入数据中出现超过2次，包括他和他反面。问满足该条件的布尔序列x有多少种。
如果忽略“超过两次”这个条件是难做的。。（好吧就是我看走眼了）
利用好这个条件，可以先把含相同x的v连边，由于一个x不会出现超过两次，一个v的度也不会超过2，那么就有可能形成环、链或点。
然后分别在环链上做DP，点特判即可。$f(i,0/1,0/1,0/1)$--前i个点，第一个点的第一个变量选了0还是1（判环用），上一次选的变量是0还是1，当前已经确定的v异或起来是0还是1。然后分极多种情况转移即可，要考虑一条边对应的x符号是否一样，详见代码。环的最后要特判，边的最初和最后要分端点的v是含一个变量还是两个。
比较难写。
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
//#include<assert.h>
#include<algorithm>
//#include<iostream>
using namespace std; int n,m;
#define maxn 200011
const int mod=1e9+;
struct Edge{int to,next,v;}edge[maxn<<]; int first[maxn],le=;
void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}
void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);} struct Node
{
int k,id[];
}a[maxn];
int appear[maxn],h[maxn][],final[maxn][],start[maxn],tot=; bool vis[maxn]; int sta[maxn],top=;
void findstart(int x,int fa)
{
vis[x]=; sta[++top]=x;
bool flag=;
for (int i=first[x];i;i=edge[i].next)
{
if (i==fa || (i^)==fa) continue;
flag=;
const Edge &e=edge[i];
if (vis[e.to]) start[tot]=e.to;
else findstart(e.to,i);
}
if (!flag) start[tot]=x;
if (flag && fa== && !start[tot]) start[tot]=x;
} int now,f[maxn][][][];
void dfs(int x,int fa)
{
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
f[x][][][]%=mod;
vis[x]=;
if (!fa)
{
if (a[x].k==) f[x][][][]=f[x][][][]=;
else f[x][][][]=;
} bool flag=;
for (int i=first[x];i;i=edge[i].next)
{
if (i==fa || (i^)==fa) continue;
const Edge &e=edge[i];
if (vis[e.to] && !fa) continue;
flag=;
bool diff;
for (int j=;j<a[x].k;j++)
for (int k=;k<a[e.to].k;k++)
if (fabs(a[x].id[j])==fabs(a[e.to].id[k]) && fabs(a[x].id[j])==e.v)
diff=(a[x].id[j]==-a[e.to].id[k]);
if (vis[e.to])
{
if (!diff)
{
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
}
else
{
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
}
}
else
{
if (!diff)
{
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][]; f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
}
else
{
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][]; f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
f[e.to][][][]+=f[x][][][];
}
dfs(e.to,i);
}
}
if (!flag)
{
if (a[x].k==)
{
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
}
else
{
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][]
+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
h[now][]=(0ll+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][]
+f[x][][][]+f[x][][][]+f[x][][][]+f[x][][][])%mod;
}
}
} int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i].k);
for (int j=;j<a[i].k;j++)
{
scanf("%d",&a[i].id[j]);
if (appear[(int)fabs(a[i].id[j])])
{
if (appear[(int)fabs(a[i].id[j])]!=i)
insert(appear[(int)fabs(a[i].id[j])],i,(int)fabs(a[i].id[j]));
else
{
vis[i]=; tot++;
if (a[i].id[]==-a[i].id[]) h[tot][]=,h[tot][]=;
else h[tot][]=h[tot][]=;
}
appear[(int)fabs(a[i].id[j])]=-;
}
else appear[(int)fabs(a[i].id[j])]=i;
}
}
for (int i=;i<=m;i++) if (appear[i]> && a[appear[i]].k==)
{
vis[appear[i]]=; tot++;
h[tot][]=h[tot][]=;
}
for (int i=;i<=n;i++) if (!vis[i]) tot++,findstart(i,);
for (;top;top--) vis[sta[top]]=;
for (int i=;i<=tot;i++) if (start[i]) now=i,dfs(start[i],); final[][]=h[][]; final[][]=h[][];
for (int i=;i<=tot;i++)
{
final[i][]=(1ll*final[i-][]*h[i][]+1ll*final[i-][]*h[i][])%mod;
final[i][]=(1ll*final[i-][]*h[i][]+1ll*final[i-][]*h[i][])%mod;
}
for (int i=;i<=m;i++) if (appear[i]==) final[tot][]=(final[tot][]<<)%mod;
printf("%d\n",final[tot][]);
return ;
}
最新文章
- UVA 820 --- POJ 1273 最大流
- Soundslice – 美妙乐谱！Web 技术高大上的应用
- Android源码剖析之Framwork层消息传递（Wms到View）
- POJ 1502 MPI Maelstrom
- Image1.Canvas画图笔刷
- Modernizr.js介绍与使用
- Windows下caffe的配置和调用caffe库（二）
- 如何在vue-cli webpack中全局引入jquery
- 爆炸，解体，入侵，你想得到的你想不到的大BUG们
- x86汇编寄存器，函数参数入栈说明
- codeforces463D
- Codeforces Round #546 (Div. 2) C. Nastya Is Transposing Matrices
- python之黏包和黏包解决方案
- 校内模拟赛 SovietPower Play With Amstar
- vue中的计算属性中的坑，
- 关于MongoDB时区问题
- 火狐FireFox恢复备份失败，无法处理备份文件
- 【最短路Dijistra】【一般堆优化】【配对堆优化】
- weX5如何绑定KO对象
- Azure 软件架构选择