【题解】UOJ114 UER #2 信息的交换 – foreverpiano

蒟蒻选手来写题解啦~

题目链接

首先有一个结论: 对于一个联通块, 经过行动后的颜色其实是按照编号从大到小 DFS 的 DFN 序.

感受一下, 对于节点 $ u $ 操作完后的颜色是编号最大的孩子 $ v $, 对于 $ v $ 的孩子也可以递归理解, 相当于插入一段 DFN 序.

由于是 DFN 序, 所以只有返祖边, 对于返祖边 $ (v, u) $合法, 其中 $ u $ 是 $ v $ 的祖先, 需要满足 $ u $ 连下来的子树 $ w $ , $ a_w < a_v $.

于是就可以直接 DP 了, 记 $ f_{i,j} $ 表示区间 $ [i,j] $ 为一颗子树的方案数, $ g_{i,j} $ 为形成若干合法森林的方案数, 转移的时候需要限制选的元素 $ a_i > a_k $, 复杂度为 $ O(n^3) $ .

#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

template<typename tp> inline void read(tp &x) {
    x = 0; char c = getchar(); int f = 0;
    for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
    if (f) x = -x;
}
namespace {
    const int mo = 998244353;
    inline int add(int x, int y) { x += y; return x >= mo ? x - mo : x; }
    inline int sub(int x, int y) { x -= y; return x < 0 ? x + mo : x; }
    inline int mul(int x, int y) { return (lo) x * y % mo; }
    inline int power(int a, int k = mo - 2) {
        int ans = 1;
        for (; k; k >>= 1, a = mul(a, a))
            if (k & 1) ans = mul(ans, a);
        return ans;
    }
    inline void U(int &x, int y) { x = add(x, y); } 
}

const int N = 555;
int g[N][N], f[N][N], h[N][N], p2[N], p[N], vis[N], a[N], m, n;

inline int doit() {
    memset(g, 0, sizeof g);
    memset(f, 0, sizeof f);
    memset(h, 0, sizeof h);
    rep (i, m) f[i][i] = g[i][i] = h[i][i] = 1;
    for (int len = 2; len <= m; len++) {
        for (int l = 1; l <= m; l++) {
            int r = l + len - 1; if (r > m) break;
            U(f[l][r], g[l + 1][r]);
        }
        for (int l = 1; l <= m; l++) {
            int r = l + len - 1; if (r > m) break;
            int cnt = 0;
            for (int k = l + 1; k <= r; k++) cnt += a[l] < a[k];
            h[l][r] = g[l][r] = mul(f[l][r], p2[cnt]);
            for (int k = l; k < r; k++)
                if (a[l] > a[k + 1]) {
                    U(g[l][r], mul(h[l][k], g[k + 1][r]));
                }
        }
    }
    return f[1][m];
}

int main(void) {
    read(n);
    p2[0] = 1; rep (i, n) p2[i] = mul(p2[i - 1], 2);
    rep (i, n) read(p[i]);
    int ans = 1;
    rep (i, n) if (!vis[i]) {
        m = 0;
        int u = i;
        while (!vis[u]) {
            vis[u] = true;
            a[++m] = u;
            u = p[u];
        }
        ans = mul(ans, doit());
    }
    cout << ans << "\n";
}