CF2034F2 题解

EuphoricStar · 2024-12-01 22:09:35 · 题解

感觉这题的转化非常神奇，场上怎么过了那么多，是我太菜了……

Easy Version 的容斥做法对 Hard Version 没有任何帮助。

容易将问题转化成，有一个 n \times m 的网格图，给定 k 个关键点 (x_i, y_i)，每次可以以一定的概率往上或往右走，往上走得分 + 1，往右走得分 + 2，每走到一个关键点得分 \times 2，求最终期望得分。

首先可以发现每条路径的概率相同，所以先求出总数再除路径数就是答案。考虑拆贡献。对于一条恰好经过了 k 个关键点 p_1, p_2, \ldots, p_k 的路径（认为 (0, 0) 和 (n, m) 也是关键点），p_{i - 1} \to p_i 这一段贡献为 2^{k - i} \times (2(r_{p_i} - r_{p_{i - 1}}) + b_{p_i} - b_{p_{i - 1}})。考虑对于每个 j \ge i，将答案累加 2^{k - j - 1} \times (2r_{p_j} + b_{p_j})，最后的期望再加上 2n + m（这么做是因为我们把 2^{k - i} 拆成了 2^{k - i - 1} + 2^{k - i - 2} + \ldots + 2^0 + 1）。

考虑 2^{k - j - 1} 相当于 p_j, p_{j + 1}, \ldots, p_{k - 1} 的子集数量，于是 2^{k - j - 1} 可以看作是选一个点 p_j 和若干个点 s_1, s_2, \ldots, s_t，表示路径依次经过了 p_j, s_1, s_2, \ldots, s_t（不要求恰好）。于是直接把所有点按字典序排序后 DP，设 f_i 为先选若干个之后的点，然后钦定路径经过了点 i 和那些点的方案数。有转移 f_i = \sum\limits_{j = i + 1}^{k + 1} f_j \binom{x_j - x_i + y_j - y_i}{x_j - x_i}。答案就是 \sum\limits_{i = 1}^k f_i \times \binom{x_i + y_i}{x_i} \times (2x_i + y_i)。

时间复杂度 O(n + m + k^2)。

code