题解 CF704C 【Black Widow】

xht

2020-03-07 23:11:18

Solution

> [CF704C Black Widow](https://codeforces.com/contest/704/problem/C) ## 题意 - 有 $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$ 看待。 然后用**至少两个点的链**的方法做即可。 ## 代码 ```cpp 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; } ```