这是一份基于你提供的代码的详细题解。

题目分析

这道题主要包含两个部分：

1. 维护每个单位的生命值状态：由于伤害是概率性的，我们需要维护每个单位剩余生命值的概率分布。
2. 处理“结界”技能的询问：计算在选定 $k$ 个单位中，恰好命中某一个存活单位的概率。这涉及到组合概率问题。

算法详解

1. 维护生命值 DP (calc1 函数)

由于每个单位的血量上限 $m_i$ 很小 ($m_i \le 100$)，我们可以对每个单位分别维护一个 DP 数组。

设 $f[i][j]$ 表示第 $i$ 个单位剩余生命值为 $j$ 的概率。

• 初始时，对于单位 $i$，有 $f[i][m_i] = 1$，其余为 0。

当对单位 $id$ 施放“锁定”技能时（命中概率 $p$）： 我们需要更新 $f[id]$ 数组。对于任意 $j > 0$，生命值从 $j$ 变为 $j-1$ 的概率是 $p$，保持为 $j$ 的概率是 $1-p$。 转移方程如下：

• $f_{new}[id][j] = f_{old}[id][j] \times (1 - p) + f_{old}[id][j+1] \times p$ （对于 $1 \le j < m_{id}$）
• $f_{new}[id][m_{id}] = f_{old}[id][m_{id}] \times (1 - p)$
• $f_{new}[id][0] = f_{old}[id][0] + f_{old}[id][1] \times p$ （生命值降为0或原本就是0都算死亡）

这一步的时间复杂度为 $O(m_{id})$。代码中的 calc1 函数正是实现了这个逻辑。

2. 处理“结界”技能 (calc3 和 calc2 函数)

对于选定的 $k$ 个单位，如果我们要计算命中单位 $u$ 的概率，公式为：

$$P(\text{命中} u) = P(u \text{存活}) \times \sum_{j=0}^{k-1} P(\text{除} u \text{以外恰好有} j \text{个单位存活}) \times \frac{1}{j+1} $$

这里 $\frac{1}{j+1}$ 是因为如果包括 $u$ 在内共有 $j+1$ 个单位存活，命中 $u$ 的概率是均等的。

为了计算这个值，我们需要知道“除 $u$ 以外恰好有 $j$ 个单位存活”的概率。如果对每个 $u$ 都做一次 $O(k^2)$ 的背包 DP，总复杂度会变成 $O(k^3)$，在 $k$ 较大时无法接受。

优化方案：退背包（除去一个物品的背包 DP）

1. 整体 DP (calc3)： 首先计算 $k$ 个单位的整体情况。设 $g[j]$ 表示这 $k$ 个单位中，恰好有 $j$ 个单位存活的概率。 这其实是一个生成函数的卷积，或者看作 0/1 背包问题。 设单位 $v$ 存活的概率为 $P_v = 1 - f[v][0]$，死亡的概率为 $Q_v = f[v][0]$。 转移方程：$g[j] = g[j] \times Q_v + g[j-1] \times P_v$。 时间复杂度 $O(k^2)$。

2. 退背包 (calc2)： 对于每个单位 $u$，我们需要从整体数组 $g$ 中“撤销”掉单位 $u$ 的贡献，得到临时数组 tmp，其中 tmp[j] 表示除 $u$ 以外恰好 $j$ 个存活的概率。 根据整体 DP 的方程，我们有： $g[j] = tmp[j] \times Q_u + tmp[j-1] \times P_u$ 移项得： $tmp[j] \times Q_u = g[j] - tmp[j-1] \times P_u$ 即：

   $$tmp[j] = \frac{g[j] - tmp[j-1] \times P_u}{Q_u}$$
   • 特殊情况：如果 $Q_u = 0$（单位 $u$ 必定存活），则 $g[j] = tmp[j-1]$，所以 $tmp[j] = g[j+1]$。
   • 代码中的 calc2 实现了这个逆推过程。f[id][0] 即为 $Q_u$，1 - f[id][0] 即为 $P_u$。计算需要用到模逆元。

3. 统计答案： 利用 tmp 数组计算最终概率： ans = $\sum_{j=0}^{k-1} tmp[j] \times \frac{1}{j+1}$ 最后乘以 $u$ 存活的概率 $(1 - f[u][0])$。

复杂度分析

• 锁定技能：每次 $O(\max(h_i)) \approx O(100)$。
• 结界技能：
  • calc3 耗时 $O(k^2)$。
  • 对于 $k$ 个目标，每个调用 calc2 耗时 $O(k)$，共 $O(k^2)$。
  • 单次结界总耗时 $O(k^2)$。
• 总复杂度： $O(Q \cdot \max(h_i) + C \cdot n^2)$。 带入数据 $n \le 200, Q \le 200000, C \le 1000$，最大计算量约为 $2 \times 10^7 + 1000 \times 40000 \approx 6 \times 10^7$，在 6000ms 的时限内非常充裕。

代码对应解读

• f[i][j]：DP 数组，表示第 i 个单位剩余血量为 j 的概率。
• calc1(id, p)：执行锁定技能，更新 f[id]。
• calc3()：对当前询问的 $k$ 个单位进行 $O(k^2)$ 的背包 DP，计算 $g$ 数组。
• calc2(id)：执行退背包操作，计算除去单位 id 后的 $tmp$ 数组。
• main 函数最后部分：计算所有技能结束后每个单位的期望生命值 $\sum j \times f[i][j]$。

总结

这是一道结合了 概率 DP 和 背包 DP（含退背包技巧） 的好题。代码逻辑清晰，利用退背包将每次询问的复杂度从 $O(k^3)$ 优化到了 $O(k^2)$，从而通过了题目。