2024.5.22
ZROI - 樂園
对于 \(n\) 个三元组 \((a_i,b_i,c_i)\) ，如果任意两个三元组互不相同，那么我们可以在 \(O(n\log n)\) 时间内求出三维偏序对的数量：
- 首先按照每一维从小到大排序，按照这个顺序重新分配每一维，使得每一维都构成一个排列
- 然后，考虑二项式反演，设 \(f_i,g_i\) 分别是恰好/钦定 \(i\) 维是偏序的点对数量，那么 \(f_0=g_0-g_1+g_2-g_3\)，同时由对称性 \(f_0=f_3=g_3\)，所以答案 \(f_3=g_3=\frac{g_0-g_1+g_2}{2}\)，\(g_0,g_1\) 容易求出，\(g_2\) 可以通过 \(3\) 个二维偏序求出。
- 时间复杂度 \(O(n\log n)\)。
ZROI - 远溯
设 \(C(x)\) 为卡特兰数的生成函数，我们考虑怎么求出 \([x^n]C(x)^m\):
solution 1
因为卡特兰数 \(C(x)=1+xC(x)^2,B(x)=C(x)-1\)，那么 \(\frac{B(x)}{(B(x)+1)^2}=x\)，\(A(x)=\frac{x}{(x+1)^2}\)为其复合逆，\(H(x)=(x+1)^m\)，那么根据扩展拉格朗日反演：
\[[x^n]H(B(x))=[x^{n-1}]\frac{1}{n}H'(x)(\frac{x}{A(x)})^n=[x^{n-1}]\frac{m}{n}(x+1)^{m-1}(x+1)^{2n}=\frac{m}{n}\binom{2n+m-1}{n-1} \]solution 2
考虑卡特兰数等价于格路计数，我们强制在每走完一段后走一步 \((+1,0)\)，这样就会走到 \((n+m,n)\)，这是一个双射，因为我们如果有一条这样的格路，只要每次找到最小的能缩的位置缩一下一定能对应到一个之前的格路。
标签：偏序,frac,回首,三元组,掩埋,一维,地被,ZROI,卡特兰 From： https://www.cnblogs.com/jesoyizexry/p/18206767