感觉是一类组合计数的综合题。刚好可以完整梳理一下。
首先长度为 \(2n\) 的合法括号串计数是最经典的问题：合法性可以转成 \(+1/-1\) 的序列来判断，则合法等价于和为 \(0\) 且任意前缀和非负。
把过程看作是在网格图上游走，也就是 \((0,0)\rightarrow (n,n)\) 且不穿过 \(y=x\) 这条直线的方案数。
我们知道这个就是卡特兰数。
卡特兰数可以对应到括号上，然后再对应到树上：任意一个 \(n+1\) 个点的有根（无标号）树都和一个长度为 \(2n\) 的合法括号序列一一对应，考虑 dfs 的过程，当我们从一个点进入它的儿子的时候打入左括号，否则打入右括号。这样一棵树对应一个合法括号序列，反过来也容易发现一个括号序列唯一对应一棵树（这个括号串建树套路似乎还是典）。
而树可以对应到二叉树，具体地，\(n+1\) 个点的有根无标号树个数就是 \(n\) 个点的有根无标号二叉树个数。（如果只有一个儿子，左右是会区分的）。
考虑二叉树转普通树：初始有一个根 \(u\)，然后选择根一直往左走到不能再走这条左链，\(u\) 连向这条链的所有点。然后考虑每个点的右儿子构建出来的若干个子树就连到这个点上。也容易发现转回去也是唯一的。
不过事实上，直接列出递推式计算也容易发现上面的这个事实。
回到本题：以 \((value,index)\) 二元组作为关键字建出大根的笛卡尔树，则两个序列相等等价于他们的笛卡尔树相同。
然而不是所有笛卡尔树都合法的：注意到若存在一个点，\(root\) 到它的路径有 \(\ge m\) 个右儿子那就不合法了。
猜测这个也是不合法的充要条件，换言之，只要满足上面的条件总能有解。
可以感知到除非 \(n\lt m\) 否则我们总能填一组数进去合法。
那么就变成了对二叉树计数，这样有一个暴力做 \(m\) 次 \(f=\frac{1}{1-xf}\) 的做法，这里暂且不展开。
二叉树的计数用上面的方法转成一般树计数，则右儿子 \(\lt m\) 的条件就变成了深度 \(\le m\)。
而 \(n+1\) 个点的树个数又等于 \(2n\) 长度的合法括号计数，所以现在的问题是：
计算长度为 \(2n\) 的合法括号序列个数，满足深度 \(\le m\)。
然后回到最开始的网格图计数上来。
下面这个方法也许被叫做反射容斥？首先可以看出来这次多加了一条直线 \(y=x+m\)，也就是被这两条直线给框住了。
如果只有一条直线，事实上存在一个容斥做法：我们考虑任何一条不合法路径都一定经过了 \(y=x+1\) 这条直线，考虑其第一次落在这里的位置，然后以 \(y=x+1\) 为直线将前面的部分对称过去（注意到 \((0,0)\) 一定对称到 \((-1,1)\)），所以任何一条 \((0,0)\) 开始的不合法路径都对应了一条 \((-1,1)\) 开始的路径；反过来 \((-1,1)\) 要到 \((n,n)\) 必须穿过 \(y=x+1\)，那么这个时候翻折回去，又唯一对应了 \((0,0)\) 开始的一条不合法路径。
所以答案为 \(\dbinom{2n}{n}-\dbinom{2n}{n-1}\)（注意到你不管怎么对称，总步数都是 \(2n\)，区别只不过在于两个维度分别要走的步数罢了）。
现在考虑加进第二条直线 \(y=x-m\)。
首先有一个辅助公式在：\((X,Y)\) 关于 \(y=x+b\) 的对称点就是 \((Y-b,X+b)\)。
注意到一条非法路径可能多次碰到两条直线，（这里有一个常规的容斥，需要分治 NTT 可以做到 \(O(n\log^2 n)\) 且常数不小），我们希望其只被计数一次。
考虑一条路径在第一次碰到上面的直线的时候算进去，之后第一次碰到下面的直线的时候排除，....；然后我们调换顺序，第一次碰到下面的直线的时候再把它算进去，之后第一次碰到上面的直线的时候再排除... 这样，不管你先碰到上面还是下面，最后这条路径就是被算了一次。
可以看出，两部分是类似的，以第一部分为例，第一次碰到上面直线，那就 \((0,0)\) 翻成 \((-1,1)\)；下一次碰到下面直线，就把 \((-1,1)\) 翻过去,....,不断这样翻，翻 \(O(n)\) 次就好了。时间复杂度 \(O(n)\)。
标签：直线,括号,路径,合法,计数,2023.5,2n From： https://www.cnblogs.com/Cry-For-theMoon/p/17369511.html