考虑对于每一个位置\(i\)，计算所有可能的结果出现的概率。
定义一个区间\([l,r]\)为对于\(x\)的极大区间，当且仅当\(\max \limits _{i=l}^r \{a_i\} \leq x < min\{a_{l-1},a_{r+1}\}\)（其中\(a_0=a_{N+1} = MOD\)）
那么我们需要考虑极大区间是如何缩小的。
考虑到设某一个点恰好为\(x\)的方案数转移还需容斥，不妨这么设状态：
设\(f_{x,p,l,r}\)表示已经进行了\(p\)次操作，且区间\([l,r]\)为对于\(x\)的极大区间的方案数。如果初始区间\([l,r]\)是对于\(x\)的极大区间，\(f_{x,0,l,r}=1\)，否则为\(0\)。
考虑转移：
①第\(p\)次修改的区间对于\([l,r]\)是否为极大区间没有影响，也就是区间同时位于\([1,l-1]\)或者\([l,r]\)或者\([r+1,N]\)，即\(f_{x,p,l,r} += f_{x,p-1,l,r} \times g_{l,r}\)，其中\(g_{l,r} = C_l^2 + C_{r-l+2}^2 + C_{N-r+1}^2\)
②第\(p\)次修改的区间的左端点小于\(l\)，右端点大于\(r\)，这种直接会让\([l,r]\)变为非极大区间，贡献为\(0\)
③第\(p\)次修改的区间有一部分在之前的\([l,r]\)，有一部分伸出去，即\(f_{x,p,l,r} += \sum\limits_{j=1}^{l-1} (j-1) \times f_{x,p-1,j,r} + \sum\limits_{j=r+1}^N (N-j) \times f_{x,p-1,l,j}\)
对于③显然是可以前缀和优化的，①中的\(g_{i,j}\)直接预处理，可以做到\(O(N^4)\)的\(DP\)
考虑计算答案，设第\(i\)个点的答案为\(ans_i\)，则有\(ans_i = \sum\limits_{j =1}^{max} j \times (\sum\limits_{m=1} ^ i \sum\limits_{p=i}^N f_{j,Q,m,p} - \sum\limits_{m=1} ^ i \sum\limits_{p=i}^N f_{j-1,Q,m,p})\)
其实到这里似乎卡卡常就能过了，因为原题数据随机
但是\(O(N^4)\)过\(400\)未免太假，所以我们需要优化算法
我们把\(ans_i\)的式子拆开
考虑对\(\sum\limits_{m=1} ^ i \sum\limits_{p=i}^N f_{j,Q,m,p}\)进行合并，除了\(j=max\)时前面的系数为\(max\)以外，其他项前面的系数是\(-1\)。也就是说每一个\(\sum\limits_{m=1} ^ i \sum\limits_{p=i}^N f_{j,Q,m,p}\)对答案的贡献为\(-1\)。又考虑到上面\(DP\)的转移式子，\(x\)的值不会影响转移方程，所以我们可以将所有\(x\)的值一起转移
故设\(g_{i,l,r}\)表示进行了\(i\)次操作，区间\([l,r]\)对答案产生的贡献的总和，转移与上面\(f\)的转移是一样的
考虑初始值，对于一个区间\([l,r]\)，如果它对于\(x\)是极大区间，则有\(\max \limits _{i=l}^r \{a_i\} \leq x < min\{a_{l-1},a_{r+1}\}\)，也就是说合法的\(x\)共有\(min\{a_{l-1},a_{r+1}\}-\max \limits _{i=l}^r \{a_i\}\)个，而每一个\(f\)对答案的贡献为\(-1\)，所以\(g_{0,l,r}=-(min\{a_{l-1},a_{r+1}\}-\max \limits _{i=l}^r \{a_i\})\)。
最后考虑一个细节：\(a_0=a_{N+1}=MOD\)。首先很显然地，\([1,N]\)需要是一个极大区间，否则会少算\(x=max\)的情况；然后对于\(f_{max,Q,i,j}\)来说，它的系数在\(ans\)中为\(max\)，所以要求\(g_{0,1,N}=max\)，也就是\(min\{a_0,a_{N+1}\}=MOD\)，所以直接赋值为\(a_0=a_{N+1}=MOD\)即可。
总复杂度\(O(N^3)\)，注意需要滚动数组压缩空间
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = (a << 3) + (a << 1) + (c ^ '0');
c = getchar();
}
return f ? -a : a;
}
const int MOD = 1e9 + 7;
int num[410] , g[410][410] , dp[2][410][410] , C[410][410] , s1[2][410][410] , s2[2][410][410] , N , Q;
void input(){
N = read();
Q = read();
for(int i = 1 ; i <= N ; ++i)
num[i] = read();
num[0] = num[N + 1] = 1e9 + 7;
}
inline int add(int a , int b){
return a + b >= MOD ? a + b - MOD : a + b;
}
inline void calc(int x){
for(int i = 1 ; i <= N ; ++i)
for(int j = 1 ; j <= i ; ++j)
s1[x][j][i] = add(s1[x][j - 1][i] , 1ll * (j - 1) * dp[x][j][i] % MOD);
for(int i = N ; i ; --i)
for(int j = N ; j >= i ; --j)
s2[x][i][j] = add(s2[x][i][j + 1] , 1ll * (N - j) * dp[x][i][j] % MOD);
}
void init(){
for(int i = 1 ; i <= N ; ++i)
for(int j = i ; j <= N ; ++j){
int maxN = 0;
for(int k = i ; k <= j ; ++k)
maxN = max(maxN , num[k]);
if(maxN < min(num[i - 1] , num[j + 1]))
dp[0][i][j] = maxN - min(num[i - 1] , num[j + 1]) + MOD;
}
for(int i = 0 ; i <= N + 1 ; ++i){
C[i][0] = 1;
for(int j = 1 ; j <= i ; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
for(int i = 1 ; i <= N ; ++i)
for(int j = i ; j <= N ; ++j)
g[i][j] = add(C[i][2] , add(C[N - j + 1][2] , C[j - i + 2][2]));
calc(0);
}
void work(){
for(int i = 1 ; i <= Q ; ++i){
for(int j = 1 ; j <= N ; ++j)
for(int k = j ; k <= N ; ++k)
dp[i & 1][j][k] = (1ll * dp[~i & 1][j][k] * g[j][k] + s1[~i & 1][j - 1][k] + s2[~i & 1][j][k + 1]) % MOD;
calc(i & 1);
}
}
void output(){
for(int i = 1 ; i <= N ; ++i){
int ans = 0;
for(int j = 1 ; j <= i ; ++j)
for(int k = i ; k <= N ; ++k)
ans = (ans + dp[Q & 1][j][k]) % MOD;
cout << ans << ' ';
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
input();
init();
work();
output();
return 0;
}