Link
利用期望的线性性，我们将一个点在Cartesian树上的深度的期望转化为期望有多少个点是这个点的祖先。
不难发现，对于排列({p})，(i)在Cartesian树上是(j)的祖先的充要条件是(p_i=minlimits_{k=min(i,j)}^{max(i,j)}p_k)。
设(f_{j-i,k})表示有多少个逆序对数为(k)的排列满足(i)在Descartes树上是(j)的祖先，那么其生成函数为：
[F_t(x)=
egin{cases}
prodlimits_{i=0}^{n-1}[i
e t]sumlimits_{j=0}^ix^j&t>0\
x^{|t|}prodlimits_{i=0}^{n-1}[i
e|t|]sumlimits_{j=0}^ix^j&t<0
end{cases}
]
那么先计算出(prodlimits_{i=1}^nsumlimits_{j=0}^ix^j=prodlimits_{i=1}^nfrac{1-x^i}{1-x})，通过暴力乘除(frac{1-x^t}{1-x})得到(F_t(x))即可，时间复杂度为(O(n^2+nk)=O(n^3))。
#include<cstdio>
const int N=50007;
int m,P,f[N],ans[N];
int read(){int x;scanf("%d",&x);return x;}
void inc(int&a,int b){a+=b-P,a+=a>>31&P;}
void dec(int&a,int b){a-=b,a+=a>>31&P;}
void mul(int k)
{
for(int i=m;i>=k;--i) dec(f[i],f[i-k]);
for(int i=1;i<=m;++i) inc(f[i],f[i-1]);
}
void div(int k)
{
for(int i=m;i;--i) dec(f[i],f[i-1]);
for(int i=k;i<=m;++i) inc(f[i],f[i-k]);
}
int main()
{
int n=read(),k=read();P=read(),m=n*(n+1)/2,f[0]=1;
for(int i=1;i<=n;++i) mul(i);
for(int i=1;i<=n;++i) ans[i]=f[k];
for(int i=2;i<=n;++i)
{
div(i);
for(int j=1;j+i-1<=n;++j) inc(ans[j],k-i+1>=0? f[k-i+1]:0),inc(ans[j+i-1],f[k]);
mul(i);
}
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
}