自动搬运

查看原文

来自洛谷，原作者为

	251Sec 祈祷着今后的你的人生，永远都有幸福的“魔法”相伴。

搬运于2025-08-24 22:46:29，当前版本为作者最后更新于2022-12-21 16:17:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文将第 $i$ 行第 $j$ 列称为 $(i, j)$。

首先发现整条路径只和起点，终点，以及在每一行你选择哪个格子向上走有关。

定义 $f_{i,j}$ 代表到达 $(i, j)$ 的方案数。

若 $(i, j)$ 有一个障碍，$(i, k)$ 有一个障碍，且 $\forall p \in [j+1,k-1]$，$(i, p)$ 没有障碍，则 $\forall p \in [j+1, k-1], f_{i,p}=\sum\limits_{s=j+1}^{k-1}f_{i-1, s}$。且 $f_{i,j}=f_{i,k}=0$。换句话说，对于这些格子，我们都可以先向上移动一格，然后左右移动到达 $(i,p)$。

注意到 $f$ 的第一维可以压掉，并且转移是区间求和与区间覆盖的形式，所以可以用线段树优化。

但是考虑到 $n, m$ 的数量级，时间和空间都无法承受。注意到 $q$ 很小，必定会出现连续的很多行没有障碍，可以使用快速幂直接转移。空间上的问题可以直接使用动态开点线段树来解决，当然更好的方案是离线下来离散化。