P15381 雨き声残響 题解

· · 题解

可能更好的阅读体验

先不考虑结束在 (x, y) 的限制，考虑刻画合法路径的形态。可以发现，路径一定是类似以下的形式：

黄色段的情况是基本固定的，所以我们先考虑红色段和蓝色段的方案数。

红色段一定是许多“S”型拐弯拼在一起的，就像这样：

考虑设 f_{i, 0 / 1} 表示填满长度为 i 的前缀并结束于 (1, i) 或 (3, i) 的方案数，转移考虑每次延长最后一个拐弯，或者新增一个新的拐弯，可以推出转移方程：f_{0, 0} = 1, f_{1, 1} = 1, f_{i, 0} = f_{i, 1} = f_{i - 1, 0} + f_{i - 1, 1}。当然你也可以推出 f_{i, 0} = f_{i, 1} = 2^{i - 2} (i > 1)。

蓝色段一定是许多“拱形”拼在一起的，就像这样：

每一段拱形长度都是 2，要么第一列往下拱，要么第三列往上拱。设 g_i 表示从左上进入，左下回来并填满一个长度为 i 的后缀的方案数，则 g_i 显然等于 (i \bmod 2) \times 2^{\lfloor{\frac i2}\rfloor}（即 i 是偶数时不存在合法方案）。

考虑 (x, y) 也是简单的，大概分类讨论一下：

  1. 先把 n < 3 的情况判掉。
  3. 1. 先把 $y = n$ 的情况判掉，答案显然为 $f_{n, [x = 1]}$。 2. 接下来枚举不存在黄色部分的方案数。方案数显然为 $f_{y - 1, [x = 1]}g_{n - y + 1}$。 3. 如果黄色部分存在，则长度至少为 $3$。前缀长度任意，后缀长度固定为 $n - y - 1$，方案数为 $g_{n - y - 1}\sum_{l = 0}^{y - 2} f_{l, [x = 1]}$。

预处理出 f, g 以及前缀和即可做到 \mathcal O(1) 查询，当然也可以都化简成 2^k 的形式，可做到无需预处理并 \mathcal O(\log n) 查询，但是本题对时间复杂度要求是 \mathcal O(n + T)。