其中$g(l,r)$为无用操作的数量。

那么答案为

其中$h(i,j)$表示位置i的值$\le val[j]$（$val$为权值从小到大排序的数组）的方案数：

这样直接做貌似是$O(n^4)$的，但是因为数据随机，所以实际上是$O(n^2q)$的。

有没有严格的算法呢？答案是有的。

注意到$f(v,i,l,r)$实际对答案的贡献为$f(v,i,l,r)(val[v]-val[v+1])$

那么我们可以直接带着总贡献DP，也就是我们设$dp(i,l,r)=\sum_v f(v,i,l,r)(val[v]-val[v+1])$

实际的转移方程是不变的。

#define N 405
const int inf=1e9;
int n,m;
int a[N];
int dp[2][N][N];
int sdp[2][N][N],tdp[2][N][N];
int g[N][N];
il int C2(int n) {return (LL)n*(n+1)/2%md;}
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
	// freopen("ot.out","w",stdout);
#endif
	in(n,m);
	for(ri i=1; i<=n; ++i) in(a[i]);
	a[0]=a[n+1]=inf;
	int cur=0,pre=1;
	for(ri l=1; l<=n; ++l)
	{
		int mx=a[l];
		for(ri r=l; r<=n; ++r)
		{
			ckmax(mx,a[r]);
			if(mx<min(a[l-1],a[r+1]))
				dp[cur][l][r]=(mx-(l==1&&r==n?0:min(a[l-1],a[r+1]))+md)%md;
			g[l][r]=add(C2(l-1),C2(r-l+1),C2(n-r));
		}
	}
	for(ri i=1; i<=m; ++i)
	{
		for(ri l=1; l<=n; ++l)
		{
			for(ri r=l; r<=n; ++r)
				sdp[cur][l][r]=add(sdp[cur][l-1][r],mul(dp[cur][l][r],l-1));
			for(ri r=n; r>=l; --r)
				tdp[cur][l][r]=add(tdp[cur][l][r+1],mul(dp[cur][l][r],n-r));
		}
		swap(cur,pre);
		for(ri l=1; l<=n; ++l)
			for(ri r=l; r<=n; ++r)
				dp[cur][l][r]=add(mul(dp[pre][l][r],g[l][r]),sdp[pre][l-1][r],tdp[pre][l][r+1]);
	}
	for(ri i=1; i<=n; ++i)
	{
		int ans=0;
		for(ri l=1; l<=i; ++l)
			for(ri r=i; r<=n; ++r) inc(ans,dp[cur][l][r]);
		out(ans,' ');
	}
	return 0;
}