题解 CF704C 【Black Widow】

· · 题解

CF704C Black Widow

题意

题解

将每个表达式看成一个点。定义一个点的值为这个点对应的表达式的值，一个连通块的值为连通块内点的值的异或，整个图的值为所有连通块的值的异或。我们要求的就是整个图的值为 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;
}