「CF2034F2」Khayyam's Royal Decree (Hard Version)
思路&做法先将题目变换一下，对于每个卷轴 \((r_i, b_i) \leftarrow (n - r_i, m - b_i)\) ，要求从 \((0, 0)\) 走到 \((n, m)\) 的所有路径的权值之和除以 \(\binom{n + m}{n}\) 。
设路径 \(p\) 经过的卷轴依次为 \(q_1, q_2, \dots , q_t\)，上述文字转化成式子即
\[\frac{\sum_p \binom{r_{q_1} + c_{q_1}}{r_{q_1}} \sum_{i = 2}^{t} (2r_i + c_i - 2r_{i - 1} - c_{i - 1}) \times 2^{t - i + 1}}{\binom{n + m}{n}}\]
分子中 \((2r_i + c_i - 2r_{i - 1} - c_{i - 1}) \times 2^{t - i + 1}\) 表示在从卷轴 \(q_{i - 1}\) 到卷轴 \(q_i\) 之间选择的宝石会在第 \(q_i, q_{i + 1}, q_{i + 2}, \dots , q_{t}\) 个卷轴处进行 \(\times 2\) 的操作。
考虑简化分子，分离 \(i - 1\) 和 \(i\) 可得
\[\sum_p \sum_{i = 1}^{t} [(2r_{q_i} + c_{q_i}) - (2r_{q_{i - 1}} + c_{q_{i - 1}})] \times 2^{t - i + 1} \\\Leftrightarrow \sum_p \sum_{i = 1}^{t - 1} (2r_{q_i} + c_{q_i}) \times 2^{t - i} - (2r_0 + c_0) + (2n + m)\\\Leftrightarrow \sum_p \sum_{i = 1}^{t} (2r_{q_i} + c_{q_i}) \times 2^{t - i}\]
令 \(p_i\) 表示以 \((r_i, c_i)\) 为开头，\((n, m)\) 为结尾的路径，\(|p|\) 表示路径 \(p_i\) 所经过的除 第\(i\) 个以外的卷轴数，上式变为
\[\sum_{i = 1}^{k} (2r_i + c_i) \sum_{p_i} 2^{|p|} \]
现在难在如何计算 \(\sum_{p_i} 2^{|p|}\) 。定义 \(f_i\) 为从卷轴 \(i\) 到 \((n, m)\) ，钦定经过若干卷轴的方案数，即
\[\sum_{s \subseteq All} \prod_{i = 1}^{|s| - 1} \binom{r_{s_{i + 1}} + c_{s_{i + 1}} - r_{s_i} - c_{s_i}}{r_{s_{i + 1}} - r_{s_i}}\]
我们发现对于一条路径 \(p_i\) ，它所经过的卷轴可以任意选择 or 不选择，即一条路径在 \(f_i\) 中会被重复统计 \(2^{|p|}\) 次，所以 \(f_i = \sum_{p_i} 2^{|p|}\) ，所以
\[\sum_{i = 1}^{k} (2r_i + c_i) \sum_{p_i} 2^{|p|} = \sum_{i = 1}^{k} (2r_i + c_i) f_i\]
对于 \(f_i\) ，我们可以通过 \(O(N^2)\) 的预处理处理出来，转移方程即 \(f_i = \sum_{r_j \geq r_i, c_j \geq c_i} f_j \times \binom{r_j + c_j - r_i - c_i}{ r_j - r_i}\) 。
最后发现在第 \(1\) 个卷轴前的宝石的路径方案数未统计，所以还需 $\times \binom{r_i + c_i}{r_i} $ 。
最后答案为
\[\sum_{i = 1}^{k} (2r_i + c_i) f_i \times \binom{r_i + c_i}{r_i}\]
solution
/*address:https://codeforces.com/problemset/problem/2034/F2AC 2025/8/18 17:29*/#includeusing namespace std;typedef long long LL;typedef pair pii;#define mkp make_pairconst int N = 4e5 + 5, K = 5005;const int mod = 998244353;LL fac, inv;inline void init() {s fac = inv = fac = inv = 1; for (int i = 2;i
页:
[1]