题意：对于逆序对数为 \(k\) 的长为 \(n\) 的排列，建出笛卡尔树，求对于每个点 \(i\) 在所有树中的深度之和。
做法：
首先不考虑笛卡尔树的事情，我们只算满足条件的排列个数，这个是经典的可以 \(O(n^3)\) 解决的问题。就是对于 \(i\)，我们只需要考虑他新增了 \([0,i-1]\) 个逆序对，做背包即可。
考虑如何刻画每个点的深度，其实是左侧递增单调栈加上右侧单调栈长度之和再加上自己这一个点。直接刻画整个单调栈也很困难，所以我们考虑拆分贡献，枚举对于 \(u,v\) 这两个点，\(v\) 要是 \(u\) 的祖先有多少种方案。那么对于 \(u<v\)，就要求 \((u,v)\) 中的数都要比 \(v\) 大，只需要 \(v\) 的位置至少产生 \(v-u\) 个逆序对；对于 \(u>v\)，那就要求 \((v,u]\) 这个区间每个数逆序对上限都减一。这个东西很容易用 \(n^3\) 的 dp 跑出来，但是这样还是太慢了。
考虑一个事情，其实我对于长度为 \(n\) 的排列我需要去推 \(n+1\) 长的排列，其实我只要在首尾加方案数是一样的。那么对于 \(u<v\) 我考虑这么加：先从左到右加入 \([u,v]\)，再向两边拓展，那么就要求 \(v\) 产生的为 \(0\)。同时注意到，因为这个东西本质上其实和多项式卷积完全一样，所以我随机交换卷的顺序是完全没问题的，我就可以把 \(v\) 的加入放到最后。发现一个很神奇的事情，这样和我只计算满足排列的个数的 dp，同样也把 \(v\) 的加入放到最后，其实只有最后这一个位置加入的不同。所以我们就可以直接 \(O(n^2)\) 回退而不需要完全重新计算。对于 \(u>v\)，其实可以认为是 \([u,v]\) 从右往左扫，分析同上。所以对于 \(|v-u|\) 相同的都可以一样一起解决，这样就是 \(O(n^3)\) 的了。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 305;
int n, mod, k, f[maxn * maxn], s[maxn * maxn], ans[maxn];
void add(int x) {s[0] = f[0];for (int i = 1; i <= k; i++)s[i] = (s[i - 1] + f[i]) % mod;for (int i = 0; i <= k; i++)f[i] = (s[i] - (i >= x - 1 ? s[i - x - 1] : 0) + mod) % mod;
}
void ers(int x) {s[0] = f[0];for (int i = 1; i <= k; i++)s[i] = (f[i] - f[i - 1] + mod) % mod;for (int i = 0; i <= k; i++)f[i] = (i >= x + 1 ? s[i] + f[i - x - 1] : s[i]) % mod;
}
signed main() {cin >> n >> k >> mod;f[0] = 1;for (int i = 1; i <= n; i++) add(i - 1);for (int i = 1; i <= n; i++)ans[i] = f[k];for (int i = 1; i <= n - 1; i++) {ers(i);for (int j = 1; j <= n - i; j++) {if(i <= k)ans[j] += f[k - i], ans[j] %= mod;ans[j + i] += f[k], ans[j + i] %= mod;}add(i);}for (int i = 1; i <= n; i++)cout << ans[i] << " ";return 0;
}
/*
3 3 10000007
*/