\(\text{反射容斥 学习笔记}\)
网上关于这部分的内容大多不是很完善，或许是网上关于反射容斥最全的一篇学习笔记？
单线容斥
- 问题引入：在坐标系上从 \((0,0)\) 走到 \((n,m)\)，每次只能顺着格点向右或者向上走一步，问方案数。
这个是入门组内容啊，在 \(n+m\) 步中任选 \(n\) 步向右，其余向上，因此方案数是 \(\binom{n+m}{n}\)。
- 问题升级：在坐标系上从 \((0,0)\) 走到 \((n,m)\)，每次只能顺着格点向右或者向上走一步，但不能越过一条线 \(y=x\)，即只能在右下三角中走，问方案数。
对于 \(m=n\) 的情况我们知道答案是卡特兰数。这个东西的证明虽然很简单但还是再重复一遍：
考虑容斥原理，用总路径数减去越过 \(y=x\) 的路径数。总路径数显然是 \(\binom{2n}{n}\)，考虑计算越过 \(y=x\) 的路径数，显然等价于路径触碰了 \(y=x+1\)，考虑将在第一次触碰 \(y=x+1\) 后的路径关于 \(y=x+1\) 对称，这样终点变成了 \((n-1,n+1)\)，可以发现这样的方案数和原先不合法的方案数是一一对应的，方案数为 \(\binom{2n}{n+1}\)，因此合法路径方案数是 \(\binom{2n}{n}-\binom{2n}{n+1}\)。
图示：
- 问题拓展：在坐标系上从 \((0,0)\) 走到 \((n,m)\)，每次只能顺着格点向右或者向上走一步，但不能越过一条线 \(y=x+b\)，即只能在右下一个梯形中走，求方案数。
根据点关于直线的对称公式可以知道点 \((x,y)\) 关于直线 \(y=x+k\) 对称后的点坐标为 \((y-k,x+k)\)，因此方案数根据类似的推导可以知道是 \(\binom{n+m}{n+b}\)。
双线容斥
- 问题进一步升级：在坐标系上从 \((0,0)\) 走到 \((n,m)\)，每次只能顺着格点向右或者向上走一步，但不能触碰两条线 \(y=x+b\) 和 \(y=x+c\) 且有 \(c\le b\)，问方案数。
仍然考虑容斥计算，naive 的想法是用全集减去触碰 \(b\) 的方案和触碰 \(c\) 的方案再加上都触碰过的方案，诸如此类。但是这个东西的问题是我们并没有保证在触碰某一条线之前没有再触碰过另一条线，因此这时的容斥较为复杂，应当是 \(f(\varnothing)-f(b)-f(c)+f(bc)+f(cb)-f(bcb)\cdots\) 这样的形式，\(f\) 里面的东西指的是钦定先后选择触碰了哪些线。那么我们的算法就是不断地对称，例如计算 \(f(b)\) 的时候将点关于 \(y=x+b\) 对称，在计算 \(f(bc)\) 的时候先将 \(y=x+c\) 关于 \(y=x+b\) 对称得到当前意义下新的线，再用 \(f(b)\) 的终点坐标按照这个线对称过去得到真实的坐标。按理说到这一步就能直接做了，复杂度是对称次数，注意到组合数内的下指标只有为自然数才有意义，而每次对称会偏移 \(b-c\) 个单位，因此复杂度是 \(O(\frac{n+m}{b-c})\) 的。
但是每次对称去写还是有些吃操作了，有没有更简单粗暴的通项公式呢？有的兄弟有的，但在这之前我们先需要一些小小的预备知识。
- 将一个点 \((x,y)\) 依次关于直线 \(y=x+a_1,y=x+a_2,y=x+a_3,\cdots,y=x+a_k\) 对称，记 \(S=\sum (-1)^{i-1}a_i\)，当 \(n\) 为奇数时变换等价于对 \(y=x+S\) 对称即变换到 \((y-S,x+S)\)；当 \(n\) 为偶数时等价于由 \((x,y)\) 变换到 \((x+S,y-S)\)。
还是应用对称点的坐标来归纳证明，从小的情况向大的情况分奇偶推导就是正确的。
那么我们可以得到以下的式子：
-
若我们先对称 \(y=x+b\)：
- 当 \(k\) 为奇数的时候，第 \(n\) 次对称时的 \(S=x+b+\frac{k-1}2(b-c)\)。
- 当 \(k\) 为偶数的时候，第 \(n\) 次对称时的 \(S=x+\frac k2(b-c)\)
-
若我们先对称 \(y=x+c\)：
- 当 \(k\) 为奇数的时候，第 \(n\) 次对称时的 \(S=x+c-\frac{k-1}2(b-c)\)。
- 当 \(k\) 为偶数的时候，第 \(n\) 次对称时的 \(S=x-\frac k2(b-c)\)。
那么我们也可以得到经过 \(n\) 次变换之后的点坐标了：
-
若我们先对称 \(y=x+b\)：
- 当 \(k\) 为奇数的时候，终点的最终坐标为 \((m-b-\frac{k-1}2(b-c),n+b+\frac{k-1}2{(b-c)})\)；
- 当 \(k\) 为偶数的时候，终点的最终坐标为 \((n-\frac k2(b-c),m+\frac k2(b-c))\)。
-
若我们先对称 \(y=x+c\)：
- 当 \(k\) 为奇数的时候，终点的最终坐标为 \((m-c+\frac{k-1}2(b-c),n+c-\frac{k-1}2(b-c))\)。
- 当 \(k\) 为偶数的时候，终点的最终坐标为 \((n+\frac k2(b-c),m-\frac k2(b-c))\)。
好的现在我们可以试图写出更通用的式子了，这里我们认为 \(k>0\)，\(ans=\binom{n+m}{n}+\sum_{k>0}(-1)^kf(k)\)：
当 \(k\) 为奇数，令 \(2r+1=k\)：
当 \(k\) 为偶数，令 \(2r=k\)：
根据答案式加起来就得到：
复杂度还是 \(O(\frac{n+m}{b-c})\) 的，看上去啥用没有对吧，但是注意到这两项的下指标都是一个公差为 \(b-c\) 的等差数列，因此这样推出来的式子有时候会有一些神秘小用处。
Ex
- 问题的改编版：在坐标系上从 \((0,0)\) 走到 \((n,m)\)，每次可以向右上 \((x+1,y+1)\) 走一步或右下 \((x+1,y-1)\) 走一步，不能触碰 \(y=b\)，问方案数。（扩展：同样也不能触碰 \(y=c\)）。
其实这类问题的解决方法是通用的，就是转坐标系，然后对应转化为单线容斥和双线容斥就和上面的东西是一样的了。我们将原先的坐标系顺时针旋转 \(45°\)，再缩小到原先的 \(\frac{\sqrt2}2\)，那么直线 \(y=b\) 就会变成 \(y=x+b\)，点 \((x,y)\) 会变成点 \((\frac{x-y}2,\frac{x+y}2)\)。这样一来问题就又变得套路化了。
例题
好吧我承认我就是为一道题写了一篇学习笔记。
CF1967E2 Again Counting Arrays
如果您认真阅读并理解了以上的全部内容，相信这道 *3500 对你来说简直就是易如反掌了。
考虑容斥，统计不合法的路径方案数。一个简单的贪心是既然 \(b\) 数组没有上限，那么当 \(b\) 能 \(+1\) 时尽量 \(+1\) 一定是更优的。不合法的时候当且仅当 \(b_i<0\)，注意到 \(a_{i+1}=b_i+1\) 时 \(b_i\) 只能 \(-1\)，那么 simple 的想法是枚举 \(b_i\) 第一次触碰 \(y=-1\) 的位置 \(t\)，反射容斥去做，要求是不能触碰 \(y=m\) 和 \(y=-1\)。这个反射容斥是要旋转坐标系的。最终答案要乘上前面 \(b_i+1\) 时的系数 \(m-1\) 和后面乱走的方案数 \(m\) 的一些次方。E1 的根号分治就是基于 \(m\) 的值分别设计 \(O(nm)\) 的 dp 和 \(O(\frac{n^2}m)\) 的反射容斥。考虑正解。看上去枚举 \(t\) 这个行为很蠢。最终乱走乘上的系数是 \(m\)，还是按照 \(+1\) 的系数为 \(m-1\)，\(-1\) 的系数是 \(1\) 这样设计系数最终加起来一定还是对的。于是我们可以枚举终点的位置。你以为这就可以直接套最底下反射容斥的公式了对吧，那么恭喜你你还是太 naive 了，首先我们要求的是不合法的方案数，要求第一次碰到的是下边界 \(c\)，因此实际上容斥应该写成的形式是 \(f(c)-f(bc)+f(cbc)-\cdots\) 的形式。并且在下边界 \(c\) 处并不用反转，因此计算时列出来的式子应该长 \(f(\varnothing)-f(b)+f(bc)-\cdots\) 这个样子，按照上边推出来的公式往里面带值就可以了。列出来发现是一个 \(\sum_p d_p\sum_k\binom{n}{x-km}\) 的形式，其中 \(d\) 是系数，\(x-ky\in[0,n]\)。那么我们唰地一下就会做了，这不就是 \(\sum_{i=0}^nc_i\binom{n}{i}\) 的形式吗，我们只需要维护系数 \(c_i\) 就行了，而内部有贡献的地方不是关于 \(m\) 的等差数列吗？这个随便差分一下不就做完了，具体的式子可以自己根据上面的方法推一推，代码也不用给了。
参考资料 & 特别鸣谢
反射容斥学习笔记 - Sumering - 博客园
题解：CF1967E2 Again Counting Arrays (Hard Version) - 洛谷专栏
DeepSeek | 深度求索
编写匆忙，如有疏漏请联系作者指出，不胜感激。