题解：
-
我想这题时卡死在枚举每个点求答案，结果最优也只能(O(n^4))，要多从整体看。
-
考虑对整体来做，枚举(x)，表示求(le x)的方案数（经过尝试得到这个好算），(x)可以是离散后的，转换真正的答案显然。
-
考虑大于(x)的数把序列分成了若干段，对每一段做dp(f[i][u][v])表示(i)步后(a[u-1]>x,a[v+1]>x,a[u..v]le x)的方案数。
-
转移显然。
-
最后给(Ans[t][le x] += f[q][u][v] (tin[u,v]))即可。
-
这个因为随机大概是(O(n^3 *log~n))
-
考虑拆式子，设离散后是(d[1..d0])，那么真正答案是(sum_{i=1}^{d0} (le d[i] - le d[i-1]方案数)*d[i])
-
(=sum_{i=1}^{d0-1} (le d[i]方案数)*(d[i+1]-d[i])+(le d[d0])*d[d0])
-
把这个作为dp的初值即可(O(n^3))。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 1e9 + 7;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 405;
ll c[N][N];
ll c2[N];
int n, q;
ll a[N];
ll d[N], d0;
ll b[N][N];
ll e[N], e0;
ll f[2][N][N]; int o;
ll ans[N];
int main() {
fo(i, 0, 400) {
c[i][0] = 1;
fo(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
c2[i] = i * (i + 1) / 2;
}
scanf("%d %d", &n, &q);
fo(i, 1, n) scanf("%lld", &a[i]), d[++ d0] = a[i];
sort(d + 1, d + d0 + 1);
d0 = unique(d + 1, d + d0 + 1) - (d + 1);
fo(i, 1, d0) {
e0 = 0;
fo(j, 1, n) if(a[j] > d[i])
e[++ e0] = j;
e[0] = 0; e[e0 + 1] = n + 1;
fo(j, 1, e0 + 1) {
int x = e[j - 1], y = e[j];
if(x + 1 < y) {
ll v = i == d0 ? d[i] : (d[i] - d[i + 1]);
f[o][x + 1][y - 1] = (f[o][x + 1][y - 1] + v) % mo;
}
}
}
fo(i, 1, q) {
fo(x, 1, n) fo(y, x, n) {
f[!o][x][y] = f[o][x][y] * (c2[x - 1] + c2[n - y] + c2[y - x + 1]) % mo;
}
fo(x, 1, n) {
ll s = 0;
fd(y, n, x) {
f[!o][x][y] = (f[!o][x][y] + s) % mo;
s = (s + f[o][x][y] * (n - y)) % mo;
}
}
fo(y, 1, n) {
ll s = 0;
fo(x, 1, y) {
f[!o][x][y] = (f[!o][x][y] + s) % mo;
s = (s + f[o][x][y] * (x - 1)) % mo;
}
}
o = !o;
}
fo(x, 1, n) fo(y, x, n)
fo(i, x, y) ans[i] = (ans[i] + f[o][x][y]) % mo;
fo(i, 1, n) {
ans[i] = (ans[i] % mo + mo) % mo;
pp("%lld ", ans[i]);
}
}