起源：将这个 dp 式子优化到线性。
\[dp_{i,j} = \sum \limits_{k = j + 1 - b - a}^{j + 1}{dp_{i-1, k}} \]考虑一个二维平面上，只能向右边或者上面走。也就是，当你走到 \((x,y)\) 的时候，你可以走到 \((x + 1, y)\) 或者 \((x, y + 1)\)。
容易发现，走到 \((n, m)\) 的方案数为 \(\dbinom{n + m}{n}\)。
如果有一条线 \(y = x + b\) 不可碰撞：
对于所有碰到这条线的，从第一次触碰开始反转，结束位置会变成 \((n,m)\) 关于 \(y=x+b\) 对称的点 \((m-b,n+b)\)。（如何推导？\(y=x+b\) 分别和 \(y=m,x=n\) 的交点的 \(x,y\) 坐标。）
容易发现一条走到 \((m-b,n+b)\) 的线翻折之后对应的都是一条经过了 \(y=x+b\) 的路线。（这里指的是如果碰到线上一个点也算）
因此如果把 \(\dbinom{n+m}{n}\) 记为 \(p(n,m)\)，表示 \((0,0)\) 到 \((n,m)\) 的路线个数，那么要求的答案等于 \(p(n,m) - p(m-b,n+b)\)。
如果有两条呢？\(y=x+b\) 和 \(y=x+c\)。
如果 \(b,c\) 都在终点的同一侧，可以认为是一个限制。否则形如下图：
考虑答案为：总方案数 \(-\) 经过 \(y=x+b\) 的方案数 \(-\) 经过 \(y=x+c\) 的方案数 \(+\) 两个都经过的方案数。
这个说法有一定道理。但是有个问题，两个都经过的方案数怎么算？
（默认 \(c<b\)）
这个路线，如果先对 \(y=x+b\) 翻折再对 \(y=x+(2b-c)\)（也就是 \(x=c\) 关于 \(x=b\) 的对称点）翻折会变成：
那么方案数为 \(p((n+b)-d,(m-b)+d),d=2b-c\)。
但是还有先到达 \(y=x+c\) 再到达 \(y=x+b\) 的例子。还有先到达 \(y=x+b\) 然后到达 \(y=x+c\) 再到达 \(y=x+b\) 的例子...
例如这个例子，它是 \(bcbc\)，在计算 \(bc\) 的时候，有 \(2 + 1 = 3\) 种方案和它有关。只要经过那一条长虚线，都是走过 \(bcb\) 的线；\(bcbc\) 的判断同理。在每一个 \(b\) 和后面的一个 \(c\) 处，都可以拐弯。因此，如果 \(bcbc...bc\) 串长度为 \(k\)，那么代表它的经过 \(i\) 次折叠分别为 \(bc...bc\) 的线有 \(???\) 条。例如一条路线分别穿过 \(bcbcbcbc\)，那么在终点关于 \(bcb\) 对称之后，代表它的有 \(f_?(8,3)\) 条。
那么我们需要统计的是：（一串字母表示到达线的先后，只管有没有到达，不管别的）
\(\emptyset - b -c+bc+cb-bcb-cbc+bcbc-cbcb+...\)
容易发现一次反射最少超过 \(1\) 的偏移量，而如果反射到第一象限外就没有贡献，不需要再反射了。时间复杂度 \(O(\cfrac{n+m}{b-c})\)。
标签：bcbc,方案,bc,到达,容斥,计数,反射,...,格路 From： https://www.cnblogs.com/Zeardoe/p/17003282.html