\(\mathbf{Part. 1}\)
从右往左考虑肯定没啥前途，我们考虑从上往下扫行。对于每一行，它上面的元素肯定都是单调递增的，又知道元素的值域在 \(0\) 到 \(m\)，而一行总共有 \(m\) 个数，因此每行可以被表示为 \(0\) 到 \(m\) 失去一个数后按顺序排好。因此，我们可以用一个 \(0 \leq x \leq m\) 的数来表示一行。
我们设 \(f_{i, j}\) 表示前 \(i\) 行，第 \(i\) 行失去了 \(j\) 的方案数。那么，考虑相邻两行如何转移。
首先，假设我们要从 \(i - 1\) 向 \(i\) 转移，而 \(i - 1\) 失去的是 \(x\)。分两部分：
- 对于第 \(i - 1\) 行的 \(x + 1\) 到 \(m\)，转移到 \(i\) 行后肯定是 \(x + 2\) 到 \(m\)
- 对于 \(0\) 到 \(x - 1\)，我们可以让消失的数从 \(0\) 取到 \((x + 2) - 1 = x + 1\)
上面结合具体实例理解。
假设 \(i\) 失去了 \(x\)，\(i - 1\) 失去了 \(y\)，有 \(x \leq y - 1\)，因此 \(f_{i, j} = \sum_{k = 1}^{j + 1} f_{i - 1, k} = f_{i, j - 1} + f_{i - 1, j + 1}\)。
这里将求和转化为两个数相加十分关键。
\(\mathbf{Part. 2}\)
我们观察这个 DP 式子，画出转移的图：
可以看到，有两种移动方式：向右或者向左上。不妨将这个东西转化为我们更熟悉的网格图，向右和向上。如图。
紫色是处理 \(f_{i, 0} = f_{i - 1, 0}\) 时的特殊转移。
那么，这个 DP 的式子实际上就等价于只经过图中的这些点和边，从 \((0, 0)\) 到 \((n + 1, m)\) 的方案数。
而这些边点的限制就相当于我们只能向右 / 向上走，不经过两边的斜率为 \(1\) 的斜线。
对于做括号序列比较多的同学来说，这个就比较经典了。
\(\mathbf{Part. 3}\)
我们考虑反射容斥。
如上图，我们假设左边的斜线为 \(A\)，右边的为 \(B\)，那么先容斥， 答案转化为 \(\text{ANS} - \text{先碰到到 A 的路径个数} - \text{先碰到到 B 的路径个数}\)。显然，先到 \(A\) 和先到 \(B\) 的两个问题是对称的，所以我们只考虑 \(A\)。
如上图，我们取出来这条路径第一次碰到 \(A\) 的点，将这个点之后的整条路经翻转到 \(P'\)，并观察 \(O \to P\) 先到 \(A\) 的路径和 \(O \to P'\) 的路径。实际上，这两个集合可以构成双射，证明显然。
因此，我们只需要计算 \(O \to P'\) 的路径数即可。
问题似乎解决了……吗？
\(\mathbf{Part. 4}\)
我们来想为什么这样会算错。
如上图，我们有一条经过 \(A, B\) 的路径，但在被 \(A\) 翻折一次，被 \(B\) 翻着一次后，被减了两次。
其实，\(\mathbf{Part. 3}\) 中我们计算的路径个数，只是经过 \(A\) 的路径个数，而不是先碰到 \(A\) 的路径个数。所以，我们还要加上那些被重复计算的方案，比如分别经过 \(A, B\) 和 \(B, A\) 的路径。
因此，我们定义 \(f(t)\)，其中 \(f(\texttt{AB})\) 就表示分别经过 \(A, B\) 的路径个数，\(f(\texttt{BAB})\) 就表示分别经过 \(B,A,B\) 的路径个数。只要能算出来 \(f\)，答案就是 \(\text{ANS} - f(\texttt{A}) - f(\texttt{B}) + f(\texttt{AB}) + f(\texttt{BA}) - \cdots\)。
\(\mathbf{Part. 5}\)
我们以 \(f(\texttt{AB})\) 和下图的这个路径为例，考虑如何计算 \(f\)。
这是初始的路径，设上面的对角线是 \(A\)，下面的是 \(B\)。我们先将这个路径与 \(A\) 做一遍 \(\mathbf{Part. 3}\) 的翻转（同时，把 \(B\) 也对称过去），然后再将新的路径对新的 \(B\) 做一遍翻转。如下：
设终点为 \(P\)。第一次关于 \(y=x+b\) 对称，第二次关于 \(y=x+2b−c\)（也就是 \(y = x + b\) 关于 \(y = x + c\) 对称的结果）对称。相信看到这里你已经知道大概怎么做了。
我们考虑更朴素的情况，设 \(F(S)\) 条路径对应的字符串是 \(S\)：
- 按顺序遍历字符。
- 如果是 \(A\)：\(P\) 和 \(y=x+c\) 都关于 \(y=x+b\) 对称。
- 如果是 \(B\)：\(P\) 和 \(y=x+b\) 都关于 \(y=x+c\) 对称。
- 最后得到的 \(P\) 到 \((0,0)\) 的路径数就是 \(F(S)\)。
- 如果 \(P\) 的横坐标或纵坐标小于 \(0\)，就舍去。
现在，结合 \(\mathbf{Part. 4}\) 的答案式，我们就可以解出ci'y't