一些 trick (3) | 镜像法

· · 算法·理论

有一些题目中，我们为了让一些位置的 dp 值为 0，可以复制一份相反的相加，此谓镜像法。

例 1：

ABC205E

求 (0,0) 到 (H,W) 有多少不穿过 y=x+K 的走法。

朴素做法是显然的 dp。考虑镜像法，目的是使 y=x+K+1 上的 dp 值抵消为 0。

在 (-K-1,K+1) 处放置一个 -1 的 dp 值即可，这样就是 (0,0) 到 (H,W) 的路径数减去 (-K-1,K+1) 到 (H,W) 的路径数，组合数计算即可。

例 2：

ABC309Ex

求 (0,A_i) 到 (N,B_j) 的路径数的和，其中有 (x,y)\to(x+1,y+c) 的边，c\in \{-1,0,1\}。

朴素做法是显然的 dp。考虑镜像法。反过来贴一个负数的就可以处理好边界情况。多项式优化即可。

（笔者不会多项式。咕。）

已经收录至一些 trick。

习题：CF1204E