题解 CF704C 【Black Widow】
CYJian
2020-02-24 11:16:51
考虑到 $x_i$ 和 $x_{-i}$ 一共只会出现最多两次。
我们就将每个表达式看成一个点，若某两个表达式存在 $x_i$ 或 $x_{-i}$，则将这两个表达式代表的点之间连一条边，边权为 $0/1$，表示两个表达式中， $x$ 的下标相同/不同。
不难发现，这样连出的东西一定是一堆环和链。环可以通过拆一条边变成链，成了链之后就没有后效性了，就可以考虑 dp 了。
考虑设状态 $f_{i,0/1,0/1}$ 表示，考虑到当前这个连通块的第 $i$ 个表达式，当前异或值为 $0/1$，第 $i-1$ 到第 $i$ 个表达式所共有的变量，在第 $i$ 个表达式中的值为 $0/1$ 的方案数。
转移不难考虑，就手动计算一下包括边权在内的 $8$ 种情况，算出表达式的取值以及对答案的贡献，手动转移就行了。
然后我们先考虑一些特殊一点的情况：（这里仅做整合，具体细节参见代码）
#### 一、一个表达式中同时有 $x_i$ 和 $x_{-i}$
不难发现，这个点一定对答案有一个 $1$ 的贡献。提前算好就行了。
#### 二、一个表达式中有两个 $x_i$ 或 $x_{-i}$
这样的表达式，我们就当它是只有一个的孤点就行了。（虽然不知道数据里头有没有这种情况）
#### 三、一条链的端点的表达式可能有一个只出现了一次的 $x_i$
这种情况，就考虑枚举开头那个 $x_i$ 是啥，在 $f_{1,0,x_i}$ 赋值为 $1$ 就行了。
然后对于结尾上，我们也可以枚举一下 $x_i$ 上是啥，手动算一下 $x_i$ 对最后一个位置的状态影响就行了。
#### 四、环拆链
随便选一条边，枚举 $x_i$ 的取值，然后类似第三条做就行了。
#### 五、一个点同时有两个只出现了一次的 $x_i$
不难发现，这个点有 $3$ 种情况为 $1$， $1$ 种情况为 $0$。
这个数值不难计算，但是可能在分析的时候漏了这种情况导致实现不好的情况下会算挂。
---
总之这题细节挺多，挺恶心人的，如果想不清楚可以参见代码。
$\rm Code$：
```cpp
const int MAXN = 100010;
const int mod = 1e9 + 7;
inline int Mod(int x) { return x >= mod ? x - mod : x; }
inline void Add(int&x, int y) { x += y, x -= x >= mod ? mod : 0; }
int id[MAXN];
int sgn[MAXN];
int deg[MAXN];
int vis[MAXN];
int tot;
int to[MAXN << 1];
int ne[MAXN << 1];
int rv[MAXN << 1];
int fi[MAXN];
int dg[MAXN];
inline void Link(int u, int v, int w) {
tot++;
to[tot] = v;
rv[tot] = w;
ne[tot] = fi[u];
fi[u] = tot;
}
inline void AddEdge(int u, int v, int w) {
Link(u, v, w), Link(v, u, w), ++dg[u], ++dg[v];
}
int rev[MAXN];
int sta[MAXN];
int top;
inline void dfs(int x) {
sta[++top] = x, vis[x] = 1;
for(int i = fi[x]; i; i = ne[i]) {
int u = to[i];
if(vis[u]) continue;
rev[top] = rv[i];
dfs(u);
}
}
int res[2];
int main() {
int m = ri, n = ri, c0 = 0, c1 = 0;
for(int i = 1; i <= m; i++) {
int k = ri, x, y;
if(k == 2) x = ri, y = ri;
else x = ri;
deg[i] = k;
if(k == 2) {
if(x == y) { c0++, vis[i] = 1, id[abs(x)] = i; continue; }
if(x == -y) { c1++, vis[i] = 1, id[abs(x)] = i; continue; }
}
if(id[abs(x)]) AddEdge(i, id[abs(x)], (x < 0) ^ sgn[abs(x)]);
else id[abs(x)] = i, sgn[abs(x)] = x < 0;
if(k == 2) {
if(id[abs(y)]) AddEdge(i, id[abs(y)], (y < 0) ^ sgn[abs(y)]);
else id[abs(y)] = i, sgn[abs(y)] = y < 0;
}
} res[0] = 1;
while(c0--) res[0] = res[1] = Mod(res[0] + res[1]);
while(c1--) res[0] = Mod(res[0] << 1), res[1] = Mod(res[1] << 1), swap(res[0], res[1]);
int mul = 1;
for(int i = 1; i <= n; i++) if(!id[i]) mul = Mod(mul << 1);
for(int i = 1; i <= m; i++) {
if(vis[i]) continue;
if(!dg[i]) {
vis[i] = 1;
if(deg[i] == 1) res[0] = res[1] = Mod(res[0] + res[1]);
else {
int tr0 = (res[0] + 3LL * res[1]) % mod;
int tr1 = (3LL * res[0] + res[1]) % mod;
res[0] = tr0, res[1] = tr1;
}
}
if(dg[i] == 1) {
top = 0, dfs(i);
int r0 = 1, r1 = 0, r2 = 0, r3 = 0;
if(deg[sta[1]] == 2) r2 = 1;
for(int j = 1; j < top; j++) {
int tr0, tr1, tr2, tr3;
if(rev[j]) {
tr0 = Mod(r1 + r3), tr1 = Mod(r0 + r2);
tr2 = Mod(r0 + r3), tr3 = Mod(r1 + r2);
} else {
tr0 = Mod(r0 + r3), tr1 = Mod(r1 + r2);
tr2 = Mod(r1 + r3), tr3 = Mod(r0 + r2);
} r0 = tr0, r1 = tr1, r2 = tr2, r3 = tr3;
}
if(deg[sta[top]] == 2) Add(r2, Mod(r0 + r2)), Add(r3, Mod(r3 + r1));
Add(r0, r3), Add(r1, r2);
int tr0 = (1LL * r0 * res[0] + 1LL * r1 * res[1]) % mod;
int tr1 = (1LL * r1 * res[0] + 1LL * r0 * res[1]) % mod;
res[0] = tr0, res[1] = tr1;
}
}
for(int i = 1; i <= m; i++) {
if(vis[i]) continue;
top = 0, dfs(i);
int R0 = 0, R1 = 0, r0, r1, r2, r3, Rv = 0;
for(int j = fi[sta[1]]; j; j = ne[j])
if(to[j] == sta[top]) Rv = rv[j];
r0 = 1, r1 = 0, r2 = 0, r3 = 0;
for(int j = 1; j < top; j++) {
int tr0, tr1, tr2, tr3;
if(rev[j]) {
tr0 = Mod(r1 + r3), tr1 = Mod(r0 + r2);
tr2 = Mod(r0 + r3), tr3 = Mod(r1 + r2);
} else {
tr0 = Mod(r0 + r3), tr1 = Mod(r1 + r2);
tr2 = Mod(r1 + r3), tr3 = Mod(r0 + r2);
} r0 = tr0, r1 = tr1, r2 = tr2, r3 = tr3;
}
if(Rv) R0 = Mod(r1 + r3), R1 = Mod(r0 + r2);
else R0 = Mod(r0 + r3), R1 = Mod(r1 + r2);
r0 = 0, r1 = 0, r2 = 1, r3 = 0;
for(int j = 1; j < top; j++) {
int tr0, tr1, tr2, tr3;
if(rev[j]) {
tr0 = Mod(r1 + r3), tr1 = Mod(r0 + r2);
tr2 = Mod(r0 + r3), tr3 = Mod(r1 + r2);
} else {
tr0 = Mod(r0 + r3), tr1 = Mod(r1 + r2);
tr2 = Mod(r1 + r3), tr3 = Mod(r0 + r2);
} r0 = tr0, r1 = tr1, r2 = tr2, r3 = tr3;
}
if(Rv) Add(R0, Mod(r0 + r3)), Add(R1, Mod(r1 + r2));
else Add(R0, Mod(r1 + r3)), Add(R1, Mod(r0 + r2));
int tr0 = (1LL * R0 * res[0] + 1LL * R1 * res[1]) % mod;
int tr1 = (1LL * R1 * res[0] + 1LL * R0 * res[1]) % mod;
res[0] = tr0, res[1] = tr1;
} cout << 1LL * res[1] * mul % mod << endl;
return 0;
}
```