「PKUWC2018」随机游走 题解

问题描述

给定一棵 $n$ 个节点的树，从起点 $x$ 出发随机游走（每次等概率选择相邻边）。$Q$ 次询问，每次给定集合 $S$，求首次覆盖 $S$ 中所有节点的期望游走步数（起点 $x$ 初始已覆盖）。答案对 $998244353$ 取模。

关键约束：$n \leq 18$（支持状态压缩），$Q \leq 5000$（需预处理所有子集答案）。

核心思路

解决该问题需结合 Min-Max 容斥、树形 DP 求期望 和 子集和变换，核心是将“覆盖所有节点的期望”转化为“首次击中子集的期望”的组合，再通过预处理实现快速查询。

一、Min-Max 容斥：转化期望问题

“覆盖 $S$ 中所有节点的时间”等价于“$S$ 中所有节点首次被访问的时间的最大值”（记为 $\max_{u \in S} X_u$，$X_u$ 是节点 $u$ 的首次访问时间）。
Min-Max 容斥公式将“最大值的期望”转化为“子集最小值的期望”的线性组合：

$$\mathbb{E}[\max_{u \in S} X_u] = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T|+1} \cdot \mathbb{E}[\min_{u \in T} X_u] $$

其中 $\mathbb{E}[\min_{u \in T} X_u]$ 表示“首次访问到 $T$ 中任意一个节点的期望步数”（记为 $E_T(x)$，$x$ 是起点）。

二、树形 DP：计算 $E_T(x)$

对于任意子集 $T$（记为 mask），需计算 $E_T(x)$（从 $x$ 出发首次击中 $T$ 的期望步数）。由于树无环，可通过 树形 DP 避免高斯消元，将每个节点的期望表示为父节点期望的线性函数，高效递推求解。

1. 期望方程建立

设 $E[u]$ 为从节点 $u$ 出发首次击中 $T$ 的期望步数：

• 若 $u \in T$（已在目标子集），则 $E[u] = 0$；
• 若 $u \notin T$，$u$ 有 $d$ 个邻居，每次等概率选择一个，故：$$E[u] = 1 + \frac{1}{d} \sum_{v \in \text{adj}[u]} E[v] $$（$1$ 是当前步数，$\sum E[v]/d$ 是邻居期望的平均值）。

2. 线性函数递推

由于树的层级结构，将 $E[u]$ 表示为父节点 $p$ 的线性函数 $E[u] = A[u] + B[u] \cdot E[p]$（$A[u]$ 是常数项，$B[u]$ 是父节点系数）：

• 若 $u \in T$：$A[u] = 0$，$B[u] = 0$；
• 若 $u \notin T$：设 $d$ 为 $u$ 的度数，$sA = \sum_{v \in \text{children}(u)} A[v]$，$sB = \sum_{v \in \text{children}(u)} B[v]$。代入期望方程整理得：$$A[u] = \frac{d + sA}{d - sB}, \quad B[u] = \frac{1}{d - sB} $$（除法通过模逆元计算，$998244353$ 是质数，逆元为 $a^{mod-2} \mod mod$）。

3. 根节点求解

起点 $x$ 无父节点（$E[p]$ 不存在），故 $E[x] = A[x]$，即 $E_T(x) = A[x]$。

三、子集和变换：预处理所有询问答案

根据 Min-Max 容斥公式，需计算每个子集 $S$ 的答案：

$$\text{Ans}(S) = \sum_{\emptyset \neq T \subseteq S} (-1)^{|T|+1} \cdot E_T(x) $$

通过 符号调整 和 子集和变换 预处理所有 $S$ 的答案：

1. 符号调整：对每个子集 $T$，令 $f[T] = E_T(x) \cdot (-1)^{|T|+1}$（代码中通过“偶数大小子集乘 $-1$”实现）；
2. 子集和变换：对 $f$ 做“子集前缀和”，使 $f[S] = \sum_{T \subseteq S} f[T]$，此时 $f[S]$ 即为 $\text{Ans}(S)$（直接对应询问答案）。

代码解析

1. 模运算封装

MInt 类封装了模 $998244353$ 的加减乘除（含逆元），避免手动处理模运算细节。

2. 树形 DP 计算 $E_T(x)$

对每个 mask（子集 $T$），通过 DFS 递推每个节点的 $A[u]$ 和 $B[u]$，最终 $f[mask] = A[x]$（即 $E_T(x)$）：

for (int mask = 0; mask < 1 << n; mask++) {
    auto dfs0 = [&](auto &&self, int u, int p = -1) -> void {
        Z sA = 0, sB = 0;
        int d = adj[u].size();
        for (auto v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
            sA += A[v];
            sB += B[v];
        }
        if (mask >> u & 1) { // u ∈ T，E[u] = 0
            A[u] = B[u] = 0;
        } else if (d == sB) { // 理论上不会出现（无可行路径）
            A[u] = B[u] = 0;
        } else { // 线性函数系数计算
            A[u] = (d + sA) / (d - sB);
            B[u] = Z(1) / (d - sB);
        }
    };
    dfs0(dfs0, x);
    f[mask] = A[x]; // E_T(x) = A[x]
}

3. 符号调整与子集和变换

// 符号调整：f[mask] = E_T(x) * (-1)^(|mask|+1)
for (int i = 0; i < 1 << n; i++) {
    if (__builtin_parity(i) == 0) { // 偶数大小子集，乘 -1
        f[i] *= -1;
    }
}

// 子集和变换：f[mask] = sum_{T⊆mask} f[T]
for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1 << n; j++) {
        if (j >> i & 1) { // j 包含 i，累加 j^i（去掉 i 的子集）
            f[j] += f[j ^ (1 << i)];
        }
    }
}

4. 处理询问

将询问的集合 $S$ 转为二进制 mask，直接输出 $f[mask]$：

while (q--) {
    int mask = 0, k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int x; cin >> x;
        mask |= 1 << (x - 1); // 转为 0-based
    }
    cout << f[mask] << "\n";
}

复杂度分析

• 预处理：
  • 树形 DP：$O(2^n \cdot n)$（$2^{18}=262144$，$262144 \times 18 \approx 4.7 \times 10^6$）；
  • 子集和变换：$O(n \cdot 2^n)$（同树形 DP 量级）。
• 询问：$O(Q)$（$Q \leq 5000$，每次直接查预处理结果）。

总复杂度高效，可满足题目约束。

总结

本题的核心是通过 Min-Max 容斥将复杂的“全覆盖期望”转化为可计算的“子集击中期望”，再利用树的结构特性通过线性函数递推避免高斯消元，最后通过子集和变换预处理所有答案，实现快速查询。该思路充分利用了 $n \leq 18$ 的状态压缩优势，是小节点数树上期望问题的经典解法。