题解 「TAOI-1」Pentiment

· · 题解

下文将第 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 很小，必定会出现连续的很多行没有障碍，可以使用快速幂直接转移。空间上的问题可以直接使用动态开点线段树来解决，当然更好的方案是离线下来离散化。