资讯详情

考虑dp，设计状态 \(f_i\) 表示在从未经过其他障碍物的情况下到 \(i\) 号障碍物的方案数。
同时设 \(T(Z_i \to z_j)\) 表示从障碍 \(i\) 到 \(j\) 的方案数（不管有无途经其他障碍）。
于是有转移 \(f_i = T(Z_0 \to Z_i) - \sum_{k} f_k T(Z_k \to Z_i)\).
\(T\) 的计算是简单的，在此略。