题意：
给定 \(n,K\)。
对于 \(i=1,2,3,\cdots,n\)，你需要求出在所有逆序对数为 \(k\) 个的排列中 \(i\) 位置在小根笛卡尔树上的深度之和。
数据范围：\(n \le 300,K \le \dfrac{n(n-1)}{2}\)。
思路：
我们要求的是：
\[\sum_{inv(p)=K} dep(i) \]这个 \(dep(i)\) 即 \(i\) 的祖先个数，考虑哪些节点会成为 \(i\) 的祖先，画几个例子会发现就是 \(i\) 往左或往右的单调栈中的元素。
考虑两边的贡献分开算，我们先算 \(i\) 往左的单调栈的大小和。
此时 \(i\) 右边的元素不会对答案有贡献，但是它们对逆序对数会有贡献。具体而言，对于一个 \(j>i\) 的位置，根据其相对排名，其可以贡献 \(0,1,2,\cdots, j-1\) 个逆序对。
对于左边，考虑 \(\text{dp}\)，令 \(f(i,j)\) 表示长度为 \(i\)，逆序对数为 \(j\) 的排列的单调栈大小和。
这个单调栈大小就是后缀 \(\min\) 个数。转移时每次在前面插入一个数，枚举其相对排名。如果插入的数相对排名最小，那么后缀 \(\min\) 个数加 \(1\)，同时其会与所有相对排名比他小的数组成逆序对。
利用前缀和优化容易做到 \(\Theta(n^3)\) 处理这个 \(\text{dp}\)。
而每个 \(j>i\) 的位置的贡献相当于把 \(f(i)\) 的生成函数卷上 \(x^{0}+x^{1}+\cdots x^{j-1}\)。
那么 \(i\) 处的答案为：
\[[x^k]f(i)\cdot \prod_{j>i} x^0+x^1+\cdots +x^{j-1} \]左边已经预处理过了，考虑右边。
倒着扫 \(i\)，每次右边部分多卷上一个 \(x^0+x^1+\cdots+x^{i-1}\)，这个不用 \(\text{poly}\) 科技，直接前缀和优化就行。单次 \(\Theta(n^2)\)，总复杂度 \(\Theta(n^3)\)。
求左右两边卷起来后的 \(k\) 次项系数也可以暴力。也是单次 \(\Theta(n^2)\)，总复杂度 \(\Theta(n^3)\)。
往右的单调栈的贡献与往左的是对称的，这里略去了。
这样我们就得到了一个 \(\Theta(n^3)\) 的解决算法。
标签：text,多校,贡献,2024,cdots,Theta,联考,单调,逆序 From： https://www.cnblogs.com/zzzYheng/p/18263206