反射容斥学习笔记

问题描述：考虑从$(0, s)$走到$(n, t)$，可行的步为$(1, \pm 1)$，要求不能经过$x = a$和$x = b$（$a < s, t < b$）。求路径方案数。

如果只要求不能经过$x = -1$，那么做一次反射就可以算出不合法的情况。

首先从$(0, s)$到$(n, t)$任意游走的方案数为$c(s, t) = \dbinom{n}{\frac{1}{2}(n + s - t)}$。当然如果$n + s - t$是奇数或者超过了范围那么组合数为$0$。

我们需要考虑的是交替反射的情况。假设先经过$x = a$，则不合法的情况可以描述为

$$\begin{aligned} &c(s, 2a - t) - c(s, 2b - 2a + t) + c(s, 4a - 2b - t) - \cdots \\ =& \sum_{i\ge 0} c(s, 2a - t - 2i(b - a)) -\sum_{i\ge 1} c(s, t + 2i(b-a)) \end{aligned}$$

如果先经过$x = b$：

$$\begin{aligned} &\sum_{i\ge 0} c(s, 2b - t + 2i(b-a)) -\sum_{i\ge 1}c(s, t - 2i(b-a)) \\ =&\sum_{i\ge 0} c(s, 2a - t + 2(i+1)(b-a)) -\sum_{i\ge 1}c(s, t - 2i(b-a)) \end{aligned}$$

于是我们可以得到从$s$到$t$的总的合法路径方案数为

$$\begin{aligned} &\sum_{i = 0, \pm1, \pm2, \cdots} c(s, t + 2i(b - a)) - \sum_{i = 0, \pm1, \pm2, \cdots} c(s, 2a - t + 2i(b - a)) \\ =& \sum_{i}\binom{n}{\frac{1}{2}(n + s - t + 2i(b - a))} - \sum_{i}\binom{n}{\frac{1}{2}(n + s + t - 2a + 2i(b - a))} \end{aligned}$$

假设我们想对所有的$s', t'$（$a < s', t' < b$）都计算出路径方案数。假设$b - a < n$。

如果暴力计算上面的式子，复杂度$O(n(b - a))$。观察上面的两个组合数级数，可以发现前者只与$s - t$有关，后者只与$s + t$有关。因此预处理一下即可$O(1)$计算。总复杂度$O(n + (b - a)^2)$。