CF704C Black Widow 题解

CF704C Black Widow

题意

• 有 $m$ 个布尔变量 $x_{1\dots m}$，设 $x_{-i}=\neg x_{i}$。
• 给定 $n$ 个形如 $x_i$ 或 $x_i \operatorname{or} x_j$ 的表达式，保证 $x_i$ 和 $x_{-i}$ 在所有表达式中一共只会出现最多两次。
• 询问在 $2^m$ 种不同的取值方案中，有多少种方案使得所有表达式的值的异或为 $1$。
• $n,m \le 10^5$，答案对 $10^9+7$ 取模。

题解

将每个表达式看成一个点。定义一个点的值为这个点对应的表达式的值，一个连通块的值为连通块内点的值的异或，整个图的值为所有连通块的值的异或。我们要求的就是整个图的值为 $1$ 的方案数。

由于保证 $x_i$ 和 $x_{-i}$ 在所有表达式中一共只会出现最多两次，如果两个表达式存在相同的 $x_{|i|}$，则连一条边。

假设我们求出来了每个连通块的值为 $0/1$ 的方案数，那么 dp 一次即可求出整个图的值为 $0/1$ 的方案数：

设 $c_{i,0/1}$ 表示第 $i$ 个连通块值为 $0/1$ 的方案数。

设 $f_{i,0/1}$ 表示只考虑前 $i$ 个连通块，值为 $0/1$ 的方案数。

初始状态：$f_{0,0} = 1$。

目标状态：$f_{*,1}$。

转移：$f_{i,j} = f_{i-1,j} \times c_{i,0} + f_{i-1,j \operatorname{xor} 1} \times c_{i,1}$。

现在考虑如何对于每个连通块求 $c_{0/1}$。

注意到连出来的图一定由若干个连通块组成的，而连通块只有四种形态，我们分别考虑。

一个点的链

表达式形如 $x_i$，则 $c_{0} = c_1 = 1$。

表达式形如 $x_i \operatorname{or} x_j$，则 $c_0 = 1$，$c_1 = 3$。

一个点的环

表达式形如 $x_i \operatorname{or} x_i$，则 $c_0 = c_1 = 1$。

表达式形如 $x_i \operatorname{or} x_{-i}$，则 $c_0 = 0$，$c_1 = 2$。

至少两个点的链

这种形态下，链的两端对应的表达式可能形如 $x_i$，也可能形如 $x_i \operatorname{or} x_j$。

如果形如 $x_i$，我们可以把它当做 $x_i \operatorname{or} 0$ 看待，然后依然考虑 dp。

设第 $i$ 个点上的表达式为 $x_{p_i} \operatorname{or} x_{q_i}$，其中 $x_{|q_{i-1}|} = x_{|p_i|}$。

设 $g_{i,0/1,0/1}$ 表示只考虑前 $i$ 个点，值为 $0/1$，$x_{|q_i|} = 0/1$ 的方案数。

初始状态：对于 $x_{|p_1|}$ 的每种取值，$g_{0,0,x_{|p_1|}} = 1$。

目标状态：对于 $x_{|q_{*}|}$ 的每种取值，$c_0 \leftarrow g_{*,0,x_{|q_{*}|}}$，$c_1 \leftarrow g_{*,1,x_{|q_{*}|}}$。

转移：对于 $x_{|p_i|},x_{|q_i|}$ 的每种取值，$g_{i,(x_{p_i} \operatorname{or} x_{q_i}) \operatorname{xor} j,x_{|q_i|}} \leftarrow \sum_{j=0}^1 g_{i-1,j,x_{|p_i|}}$。

至少两个点的环

随便选一条边断开，转化成至少两个点的链的形态。

对于断开处的变量，枚举它的值 $w$ 为 $0/1$，然后把两端当做 $x_i \operatorname{or} w$ 看待。

然后用至少两个点的链的方法做即可。

代码

const int N = 1e5 + 7;
int n, m, d[N], k, v[N];
vi a[N], b[N], e[N], s;
modint f[N][2], c[2], g[N][2][2], ans = 1;

void dfs(int x) {
	v[x] = k, s.pb(x);
	for (int y : e[x])
		if (!v[y]) dfs(y);
}

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

inline void solve(int o) {
	if (s.size() == 1u) {
		int x = s[0];
		if (a[x].size() == 1u) return c[0] = c[1] = 1, void();
		if (abs(a[x][0]) != abs(a[x][1])) return c[0] = 1, c[1] = 3, void();
		if (a[x][0] == a[x][1]) return c[0] = c[1] = 1, void();
		return c[0] = 0, c[1] = 2, void();
	}
	int rt = 0;
	for (int x : s)
		if (d[x] == 1) rt = x;
	c[0] = c[1] = 0;
	if (rt) {
		for (int x : s) v[x] = 0;
		s.clear(), dfs(rt);
		int x = s[0], l1 = 0, r1 = 1, l2 = 0, r2 = 1;
		if (a[x].size() == 1u) r1 = 0, a[x].pb(0);
		x = s.back();
		if (a[x].size() == 1u) r2 = 0, a[x].pb(0);
		return dp(l1, r1, l2, r2);
	}
	dp(0, 0, 0, 0), dp(1, 1, 1, 1);
}

int main() {
	rd(n), rd(m);
	for (int i = 1, o, x; i <= n; i++) {
		rd(o);
		while (o--) rd(x), a[i].pb(x), b[abs(x)].pb(i);
	}
	for (int i = 1; i <= m; i++)
		if (b[i].size() == 2u) {
			int x = b[i][0], y = b[i][1];
			e[x].pb(y), e[y].pb(x), ++d[x], ++d[y];
		} else if (!b[i].size()) ans *= 2;
	f[0][0] = 1;
	for (int i = 1; i <= n; i++)
		if (!v[i]) {
			s.clear(), ++k, dfs(i), solve(k);
			for (int j = 0; j < 2; j++)
				f[k][j] = f[k-1][j] * c[0] + f[k-1][j^1] * c[1];
		}
	ans *= f[k][1];
	print(ans);
	return 0;
}