感觉挺厉害的。
我们使用 \(f_i\) 表示恰有 \(i\) 维满足偏序的数对 \((x,y)\) 的个数，\(g_i\) 表示钦定 \(i\) 维满足偏序对的数对 \((x,y)\) 的个数。
那么对于三维偏序：
\[g_0=\dbinom{0}{0}f_0+\dbinom{1}{0}f_1+\dbinom{2}{0}f_2+\dbinom{3}{0}f_3=f_0+f_1+f_2+f_3 \]\[g_1=\dbinom{1}{1}f_1+\dbinom{2}{1}f_2+\dbinom{3}{1}f_3=f_1+2f_2+3f_3 \]\[g_2=\dbinom{2}{2}f_2+\dbinom{3}{2}f_3=f_2+3f_3 \]\[g_3=\dbinom{3}{3}f_3=f_3 \]\(g_0\) 显然等于 \(\dbinom{n}{2}\)，\(g_1\) 只需要求三遍一维偏序就可以得到，\(g_2\) 只需要求三遍二维偏序就可以得到，这样我们就可以得到一个方程组：
\[\begin{cases} f_0=f_3\\ f_0+f_1+f_2+f_3=g_0\\ f_1+2f_2+3f_3=g_1\\ f_2+3f_3=g_2 \end{cases}\]解之即可。\(f_3\) 即为答案。时间复杂度是优秀的 \(\mathcal O(n\log n)\)。
而且你会发现拓展到多维偏序貌似也是可以做的。
标签：偏序,dbinom,优秀,三维,2f,cases,3f From： https://www.cnblogs.com/DerrickLo/p/18292735