题解 P4426 【[HNOI/AHOI2018] 毒瘤】

Leasier · 2022-02-25 21:29:47 · 题解

不难想到本题可以抽象为：给定一张 n 个点、m 条边的无向图，求其可空独立集的数量 \bmod \ 998244353。

独立集问题是一个 NP 问题。但由于 0 \leq m - n + 1 \leq 11，我们可以考虑求出它的一棵生成树，并枚举非树边的两个端点是否被选中。考虑钦定其中一个端点不被选中，另一个端点任意和其中一个端点被选中和另一个端点不被选中的情况，则枚举的时间复杂度为 O(2^{m - n + 1})。

现在先考虑 m = n - 1（即原图为一棵树的情况），显然可以 dp。设 dp_{u, 0 / 1} 表示 u 不被 / 被选中时 u 子树内的方案数。

转移：dp_{u, 0} = \displaystyle\prod_{v \in son_u} (dp_{v, 0} + dp_{v, 1})，dp_{u, 1} = \displaystyle\prod_{v \in son_u} dp_{v, 0}。

答案：dp_{1, 0} + dp_{1, 1}。

考虑钦定 u 不被 / 被选中的情况，发现此时我们相当于钦定 dp_{u, 1 / 0} = 0。

于是可以动态 dp。套路地，设 dp'_{u, 0 / 1} 表示 u 不被 / 被选中时 u 子树内（不包括 u 的重儿子）的方案数。

转移：dp'_{u, 0} = \displaystyle\prod_{v \in son_u, v \neq hs_u} (dp_{v, 0} + dp_{v, 1})，dp_{u, 0} = dp'_{u, 0} (dp_{hs_u, 0} + dp_{hs_u, 1})，dp'_{u, 1} = \displaystyle\prod_{v \in son_u, v \neq hs_u} dp_{v, 0}，dp_{u, 1} = dp'_{u, 1} dp_{hs_u, 0}。

于是可以得出转移矩阵：\begin{bmatrix} dp_{hs_u, 0}\ dp_{hs_u, 1} \end{bmatrix} \begin{bmatrix} dp'_{u, 0}\ dp'_{u, 1}\\ dp'_{u, 0}\ 0 \end{bmatrix} = \begin{bmatrix} dp_{u, 0}\ dp_{u, 1} \end{bmatrix}。

直接上动态 dp 即可。注意乘法时可能会遇到 0，此时我们直接用一个栈存储更改前的状态，撤销时从栈中取出元素即可。时间复杂度为 O(n + m + 2^{n - m + 1} \log^2 n)。

代码：

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int end;
} Edge;

typedef struct Matrix_tag {
    int n;
    int m;
    ll a[3][3];
    Matrix_tag(){}
    Matrix_tag(int n_, int m_){
        n = n_;
        m = m_;
        memset(a, 0, sizeof(a));
    }
} Matrix;

typedef struct {
    int l;
    int r;
    Matrix product;
} Node;

int cnt = 0, mod = 998244353;
Matrix e(2, 2);
int root[100007], head[100007], from[17], to[17], fa[100007], depth[100007], size[100007], hs[100007], dfn[100007], rnk[100007], top[100007], bottom[100007], id[100007], mark[100007], dot[17];
ll dp1[100007][7], dp2[100007][7];
Edge edge[200007];
Node tree[400007];
stack<Matrix> s;

Matrix operator *(const Matrix a, const Matrix b){
    Matrix ans(a.n, b.m);
    for (register int i = 1; i <= a.n; i++){
        for (register int j = 1; j <= b.m; j++){
            for (register int k = 1; k <= a.m; k++){
                ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j] % mod) % mod;
            }
        }
    }
    return ans;
}

Matrix operator *=(Matrix &a, const Matrix b){
    return a = a * b;
}

inline void init(int n){
    e.a[1][1] = e.a[2][2] = 1;
    for (register int i = 1; i <= n; i++){
        root[i] = i;
    }
}

int get_root(int x){
    if (root[x] == x) return x;
    return root[x] = get_root(root[x]);
}

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs1(int u, int father){
    fa[u] = father;
    depth[u] = depth[father] + 1;
    size[u] = 1;
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (x != father){
            dfs1(x, u);
            size[u] += size[x];
            if (hs[u] == 0 || size[hs[u]] < size[x]) hs[u] = x;
        }
    }
}

void dfs2(int u){
    dp1[u][0] = dp1[u][1] = 1;
    for (int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (x != fa[u]){
            dfs2(x);
            if (x != hs[u]){
                dp1[u][0] = dp1[u][0] * (dp2[x][0] + dp2[x][1]) % mod;
                dp1[u][1] = dp1[u][1] * dp2[x][0] % mod;
            }
        }
    }
    dp2[u][0] = dp1[u][0];
    dp2[u][1] = dp1[u][1];
    if (hs[u] != 0){
        dp2[u][0] = dp2[u][0] * (dp2[hs[u]][0] + dp2[hs[u]][1]) % mod;
        dp2[u][1] = dp2[u][1] * dp2[hs[u]][0] % mod;
    }
}

void dfs3(int u, int cur_top, int &id){
    id++;
    dfn[u] = id;
    rnk[id] = u;
    top[u] = cur_top;
    if (hs[u] == 0){
        bottom[cur_top] = u;
    } else {
        dfs3(hs[u], cur_top, id);
        for (register int i = head[u]; i != 0; i = edge[i].nxt){
            int x = edge[i].end;
            if (x != fa[u] && x != hs[u]) dfs3(x, x, id);
        }
    }
}

inline void update(int x){
    tree[x].product = tree[x * 2 + 1].product * tree[x * 2].product;
}

void build(int x, int l, int r){
    tree[x].l = l;
    tree[x].r = r;
    if (l == r){
        tree[x].product = Matrix(2, 2);
        tree[x].product.a[1][1] = tree[x].product.a[2][1] = dp1[rnk[l]][0];
        tree[x].product.a[1][2] = dp1[rnk[l]][1];
        id[rnk[l]] = x;
        return;
    }
    int mid = (l + r) >> 1;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    update(x);
}

Matrix get_product(int x, int l, int r){
    if (l <= tree[x].l && tree[x].r <= r) return tree[x].product;
    int mid = (tree[x].l + tree[x].r) >> 1;
    Matrix ans = e;
    if (r > mid) ans *= get_product(x * 2 + 1, l, r);
    if (l <= mid) ans *= get_product(x * 2, l, r);
    return ans;
}

inline ll query(int u){
    Matrix product = get_product(1, dfn[u], dfn[bottom[top[u]]]);
    return (product.a[1][1] + product.a[1][2]) % mod;
}

void do_modify(int x, int pos, Matrix mat){
    if (tree[x].l == tree[x].r){
        tree[x].product = mat;
        return;
    }
    if (pos <= ((tree[x].l + tree[x].r) >> 1)){
        do_modify(x * 2, pos, mat);
    } else {
        do_modify(x * 2 + 1, pos, mat);
    }
    update(x);
}

inline ll quick_pow(ll x, ll p, ll mod){
    ll ans = 1;
    while (p){
        if (p & 1) ans = ans * x % mod;
        x = x * x % mod;
        p >>= 1;
    }
    return ans;
}

inline void modify(int u, Matrix mat){
    while (u != 0){
        Matrix pre = get_product(1, dfn[top[u]], dfn[bottom[top[u]]]), cur;
        do_modify(1, dfn[u], mat);
        cur = get_product(1, dfn[top[u]], dfn[bottom[top[u]]]);
        u = fa[top[u]];
        if (u == 0) break;
        mat = tree[id[u]].product;
        s.push(mat);
        mat.a[1][1] = mat.a[2][1] = mat.a[1][1] * quick_pow(pre.a[1][1] + pre.a[1][2], mod - 2, mod) % mod * (cur.a[1][1] + cur.a[1][2]) % mod;
        mat.a[1][2] = mat.a[1][2] * quick_pow(pre.a[1][1], mod - 2, mod) % mod * cur.a[1][1] % mod;
    }
}

inline void mustnot(int u){
    Matrix mat = tree[id[u]].product;
    s.push(mat);
    mat.a[1][2] = 0;
    modify(u, mat);
}

inline void must(int u){
    Matrix mat = tree[id[u]].product;
    s.push(mat);
    mat.a[1][1] = mat.a[2][1] = 0;
    modify(u, mat);
}

inline void rollback(int u){
    int cnt = 0;
    for (register int i = u; i != 0; i = fa[top[i]]){
        dot[++cnt] = i;
    }
    for (register int i = cnt; i >= 1; i--){
        Matrix cur = s.top();
        s.pop();
        do_modify(1, dfn[dot[i]], cur);
    }
}

ll dfs(int cur, int n){
    if (cur > n) return query(1);
    int cur_i = cur + 1;
    ll ans = 0;
    if (mark[from[cur]] != 2){
        int x = mark[from[cur]];
        mark[from[cur]] = 1;
        mustnot(from[cur]);
        ans = dfs(cur_i, n);
        rollback(from[cur]);
        mark[from[cur]] = x;
    }
    if (mark[from[cur]] != 1 && mark[to[cur]] != 2){
        int x = mark[from[cur]], y = mark[to[cur]];
        mark[from[cur]] = 2;
        mark[to[cur]] = 1;
        must(from[cur]);
        mustnot(to[cur]);
        ans = (ans + dfs(cur_i, n)) % mod;
        rollback(to[cur]);
        rollback(from[cur]);
        mark[from[cur]] = x;
        mark[to[cur]] = y;
    }
    return ans;
}

int main(){
    int n, m, k = 0, id = 0;
    cin >> n >> m;
    init(n);
    for (register int i = 1; i <= m; i++){
        int u, v, u_root, v_root;
        cin >> u >> v;
        u_root = get_root(u);
        v_root = get_root(v);
        if (u_root != v_root){
            root[u_root] = v_root;
            add_edge(u, v);
            add_edge(v, u);
        } else {
            k++;
            from[k] = u;
            to[k] = v;
        }
    }
    dfs1(1, 0);
    dfs2(1);
    dfs3(1, 1, id);
    build(1, 1, n);
    cout << dfs(1, k);
    return 0;
}