先做一遍单调栈求出来 (l_i) 和 (r_i) 表示最大值区间
然后题目转成在所有区间选择方法里面有多少是可以满足一个 (l_i le j le r_i) 的 (a_j) 被更新成了 (a_i)
然后这里分成两个部分，第一个是直接区间覆盖的，另一个是间接区间覆盖的
就变成了一个数数题
段内要 (dp)
令 (f_{p,i,j}) 表示已经把点 (i) 更新成 (a_p) 同时进行了 (j) 次的方案数
然后转移推上半天也推不出来，自闭了一中午
转移考虑控制一段不可影响的区间然后剩下的快速幂乘上去，然后中间的部分 (dp)
发现内部之间是有影响的，自己并不会处理
重新定义状态：
(f_{x,v,l,r}) 表示进行了 (x) 轮之后 (lle i le r,a_ile v) 同时 (a_{l-1},a_{r+1}ge v+1) 的方案
转移就比较好做：
[f_{x,v,l,r}=f_{x-1,v,l,r}g_{l,r}+sum_{j<l} f_{x-1,v,j,r} imes(j-1)+sum_{j>r} f_{x-1,v,l,j} imes (n-j)
]
这里 (g_{l,r}) 为瞎选区间与 ([l,r]) 无关的方案数
答案统计？（(val_j) 为离散化后的结果）
[ans=sum_{j=1}^n val_j imes(sum_{i,j}-sum_{i,j-1})
]
[sum_{i,j}=sum_{iin[l,r]} f_{j,m,l,r}
]
直接做是 (O(n^4)) 的
考虑优化：
这里每次转移的时候第一维都是固定的，所以我们把这维消掉：
[dp_{i,l,r}=sum_{j=1}^n f_{j,i,l,r}
]
转移其实没变（这里感觉理解起来没啥问题，但是下次再遇到还真不知道能不能用上）
然后初始化的时候改动一下就好了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define reg register
#define For(i,a,b) for(reg int i=a;i<=b;++i)
#define Down(i,a,b) for(reg int i=a;i>=b;--i)
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int mod=1e9+7,N=410;
int n,q,a[N],f[2][N][N],g[N][N],cur=1,ans[N],dp1[2][N][N],dp2[2][N][N];
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int del(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return x*y-x*y/mod*mod;}
inline int ksm(int x,int y)
{
int res=1; for(;y;y>>=1,x=mul(x,x)) if(y&1) res=mul(res,x);
return res;
}
inline int calc(int x){return x*(x+1)/2%mod;}
signed main()
{
n=read(); q=read(); For(i,1,n) a[i]=read();
a[0]=2e18+10,a[n+1]=2e18+10;
For(l,1,n)
{
int mx=a[l];
For(r,l,n)
{
mx=max(mx,a[r]);
if(mx<min(a[l-1],a[r+1]))
{
if(l==1&&r==n) f[cur][l][r]=mx;
else f[cur][l][r]=del(mx,min(a[l-1],a[r+1]));
} g[l][r]=add(calc(l-1),add(calc(n-r),calc(r-l+1)));
}
}
For(i,1,q)
{
For(l,1,n)
{
For(r,l,n) dp1[cur][l][r]=add(mul(f[cur][l][r],l-1),dp1[cur][l-1][r]);
Down(r,n,l) dp2[cur][l][r]=add(mul(f[cur][l][r],n-r),dp2[cur][l][r+1]);
} cur^=1;
For(l,1,n)
{
For(r,l,n) f[cur][l][r]=add(mul(f[cur^1][l][r],g[l][r]),add(dp1[cur^1][l-1][r],dp2[cur^1][l][r+1]));
}
}
For(i,1,n)
{
int sum=0;
For(j,1,i) For(k,i,n) sum=add(sum,f[cur][j][k]);
printf("%lld ",sum);
} puts("");
return 0;
}
}
signed main(){return yspm::main();}