当前位置：首页 > news >正文

反射容斥与镜像法

news 2026/4/21 20:07:42

反射容斥与镜像法

（By G2029 谭家齐）

反射容斥

单线容斥

在二维平面直角坐标系中，从 $(0,0)$ 走到 $(n,m)$ ，每次只能往右走一格或者往上走一格，问方案数。
若走的时候不能越过 $y=x+b$ 这条直线，方案数又有多少种？

第一个题目的答案应该是$\displaystyle\binom{n+m}{n} $ ，非常简单。

第二个题目其实也比较简单：

我们考虑将终点 $(n,m)$ 关于 $y=x+b$ 这条直线对称，得到一个新的点 $(m-b,n+b)$ 。（具体推导可以自行完成）

可以发现对于一个原来非法的情况，一定只存在且只存在一个到达 $(m-b,n+b)$ 的路径，使得这两个路径同构（即两个路径只是关于 $y=x+b$ 这条直线翻了一次）。

那么现在就好做了，答案应该为 $\displaystyle\binom{n+m}{n} - \binom{n+m}{n+b}$。

考虑特殊情况 $n=m$ 且 $b=0$ 显然上面的答案为卡特兰数。

双线容斥

这才是重点。

还是一个例题来举例。

在二维平面直角坐标系中，从 $(0,0)$ 走到 $(n,m)$ ，每次只能往右走一格或者往上走一格，全程中不能触碰到 $y=x+b$ 和 $y=x+c$ 两条直线，且保证 $c\leq b$，问方案数。

仍考虑容斥。

一个一般的考虑是用所有的方案减去触碰 $y=x+b$ 的，减去触碰 $y=x+c$ 的，再加上同时触碰 $y=x+b$ 和 $y=x+c$ 的方案数。

但是很明显，两条线可以来回碰，我们并不能很好的计算出上面的答案。（或者说，你并不能保证在碰到一条线前没有碰到另一条线）。

给出一些符号定义（方便表示）：

设 $f(str)$ 表示钦定先后碰了 $str$ 这些线的方案数，其中 $\forall i\in[1,size],str_i\in\{b,c\}$ 。

那么答案应为 $f(\emptyset)-f(b)-f(c)+f(bc)+f(cb)-f(bcb)\dots$ 我们要做的就是不断将路径进行对称。如 $f(b)$ 的方案数就是将路径关于 $y=x+b$ 对称。而 $f(bc)$ 就应该是先将路径关于 $y=x+b$ 对称，再关于 $y=x+c$ 关于 $y=x+b$ 的对称线对称。（这句话有点绕，稍微理解一下。。。）

理论上这样就能做了。对它稍微优化一下因为每一次的对称都会偏移 $b-c$ ，所以时间复杂度应该是 $\displaystyle O(\frac{n+m}{b-c})$ 的。

但是这样还是太吃操作了。

我们有更好用的做法。

引理

将一个点 $(x,y)$ 依次关于 $y=x+a_1,y=x+a_2,y=x+a_3 \dots y=x+a_k$ 对称，设 $S=\sum(-1)^{i-1}a_i$，则当 $k$ 为奇数的时候变换后的点为 $(y-S,x+S)$，反之为 $(x+S,y-S)$。

归纳证明即可。

那么现在对于一个已知的 $str$ ，我们来分类讨论一下。

若我们先对称 $y=x+b$ ：
- 当 $k$ 为奇数的时候，第 $k$ 次对称时候的 $S = b+\frac{k-1}{2}(b-c)$ 。
- 当 $k$ 为偶数的时候，第 $k$ 次对称时候的 $S=\frac{k}{2}(b-c)$。
若我们先对称 $y=x+c$：
- 当 $k$ 为奇数的时候，第 $k$ 次对称时候的 $S=c-\frac{k-1}{2}(b-c)$。
- 当 $k$ 为偶数的时候，第 $k$ 次对称时候的 $S=-\frac{k}{2}(b-c)$。

那么我们可以用上面的引理来快速得到对称的点了。

对于原来的 $(n,m)$ 现在我们可以分类讨论得到：

若我们先对称 $y=x+b$：
- 当 $k$ 为奇数的时候，第 $k$ 次对称后的点 $(m-b-\frac{k-1}{2}(b-c),n+b+\frac{k-1}{2}(b-c))$。
- 当 $k$ 为偶数的时候，第 $k$ 次对称后的点 $(n-\frac{k-1}{2}(b-c),m+\frac{k-1}{2}(b-c))$。
若我们先对称 $y=x+c$：
- 当 $k$ 为奇数的时候，第 $k$ 次对称后的点 $(m-c+\frac{k-1}{2}(b-c),n+c-\frac{k-1}{2}(b-c))$。
- 当 $k$ 为偶数的时候，第 $k$ 次对称后的点 $(n+\frac{k-1}{2}(b-c),m-\frac{k-1}{2}(b-c))$。

现在考虑答案 $\displaystyle answer=\binom{n+m}{n}-\sum_{k>0}(-1)^k\sum_{|str|=k}f(str)$。

那么：

对于 $k=2r+1$ ，其中 $r\in \mathbb{Z}$。

\[\begin{aligned}\sum_{r\ge 0}\binom{n+m}{n+b+r(b+c)}+\binom{n+m}{n+c-r(b-c)} &=\sum_{r\ge 0}\binom{n+m}{n+b+r(b-c)}+\sum_{r\leq -1}\binom{n+m}{n+b+r(b-c)}\\ &=\sum_{r\in \mathbb{Z}} \binom{n+m}{n+b+r(b-c)} \end{aligned}\]