UPD：加了个玄学优化，已经卡到了 $300ms$ 。
by int233 @ 2023-09-14 18:00:10
@[PwXmBjR_bYsVmG](/user/333855) 细说加了个什么优化
by Meteor_ @ 2023-09-14 18:03:41
@[Meteor_](/user/756594) 对于 $f_{i,j,k}$ ，当 $k-j> \max\limits_{i=1}^nR_i-L_i$ 时，该状态无效，剔除该部分状态。
by int233 @ 2023-09-14 18:06:12
新的代码：
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,mod2=2e9+14;
ll n,q,a[405],b[405],C[405],d[405],lasl[405],lasr[405],vsd,ans[405],c[405],L[405],R[405],vs[405][405],f[2][405][405],prel[2][405][405],sufr[2][405][405];
inline void mo(ll &x,ll y){
x=(x+y>=mod)?(x+y-mod):(x+y);
}
inline void mo2(ll &x,ll z,ll y){
x=(z+y>=mod)?(z+y-mod):(z+y);
}
inline void mo3(ll &x,ll z,ll y){
x=(x+y+z>=mod2)?(x+y+z-mod2):((x+y+z>=mod)?(x+y+z-mod):(x+y+z));
}
void DO(ll v){
ll vls=b[v],mx=2;
for(ll i=1;i<=n;i++){
d[i]=0;
c[i]=(a[i]>=vls);
if(c[i]){
L[i]=i;
}
else{
L[i]=L[i-1];
}
}
R[n+1]=n+1;
for(int i=n;i>=1;i--){
if(c[i]){
R[i]=i;
}
else{
R[i]=R[i+1];
}
}
ll cnt=0,kk=0;
for(ll i=1;i<=n;i++){
if(R[i]>=L[i]+2){
mx=max(mx,R[i]-L[i]);
cnt++;
if(lasl[i]!=L[i]||lasr[i]!=R[i]){
kk++;
}
}
}
for(ll i=1;i<=n;i++){
lasl[i]=L[i];
lasr[i]=R[i];
}
if(!kk){
for(ll i=1;i<=n;i++){
vs[v][i]=vs[v-1][i];
}
return ;
}
if(!cnt){
for(ll i=1;i<=n;i++){
vs[v][i]=vsd;
}
return ;
}
for(ll j=0;j<=n+1;j++){
for(ll k=j+2;k<=min(n+1,j+mx);k++){
f[0][j][k]=0;
}
}
for(ll i=1;i<=n;i++){
if(R[i]>=L[i]+2){
f[0][L[i]][R[i]]=1;
}
}
for(ll i=1;i<=q;i++){
for(ll j=1;j<=n+1;j++){
for(ll k=j+2;k<=min(n+1,j+mx);k++){//j<=k
mo2(prel[(i&1)^1][j][k],prel[(i&1)^1][j-1][k],f[(i&1)^1][j][k]*j%mod);
}
}
for(ll j=0;j<=n+1;j++){
for(ll k=min(n+1,j+mx);k>=j+2;k--){
mo2(sufr[(i&1)^1][j][k],sufr[(i&1)^1][j][k+1],f[(i&1)^1][j][k]*(n-k+1)%mod);
}
}
for(ll k=2;k<=min(n+1,mx);k++){
f[i&1][0][k]=f[(i&1)^1][0][k]*(C[k-1]+C[0]+C[n-k+1])%mod;
mo(f[i&1][0][k],sufr[(i&1)^1][0][k+1]);
}
for(ll j=1;j<=n+1;j++){
for(ll k=j+2;k<=min(n+1,j+mx);k++){
f[i&1][j][k]=f[(i&1)^1][j][k]*(C[k-j-1]+C[j]+C[n-k+1])%mod;
mo3(f[i&1][j][k],prel[(i&1)^1][j-1][k],sufr[(i&1)^1][j][k+1]);
}
}
}
for(ll j=0;j<=n+1;j++){
for(ll k=min(n+1,j+mx);k>=j+2;k--){
mo2(sufr[q&1][j][k],sufr[q&1][j][k+1],f[q&1][j][k]);
}
}
for(ll i=1;i<=n;i++){
vs[v][i]=0;
for(ll j=0;j<i;j++){
mo(vs[v][i],sufr[q&1][j][i+1]);
}
vs[v][i]=(vsd-vs[v][i]+mod)%mod;
}
}
int main(){
cin>>n>>q;
for(ll i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
for(ll i=1;i<=n;i++){
C[i]=C[i-1]+i;
}
sort(b+1,b+n+1);
ll qn=unique(b+1,b+n+1)-b-1;
b[qn+1]=b[qn]+10;
vsd=1;
for(ll i=1;i<=q;i++){
vsd=(vsd*C[n])%mod;
}
for(ll i=1;i<=qn+1;i++){
for(ll j=1;j<=n;j++){
vs[0][j]=vsd;
}
DO(i);
for(ll j=1;j<=n;j++){//vs[i][j]-vs[i-1][j]
//cout<<i<<" "<<j<<" "<<vs[i][j]<<endl;
ans[j]+=(vs[i-1][j]-vs[i][j]+mod)%mod*b[i-1]%mod;
ans[j]%=mod;
}
}
for(ll i=1;i<=n;i++){
cout<<ans[i]<<" ";
}
return 0;
}
```
by int233 @ 2023-09-14 18:06:40
@[PwXmBjR_bYsVmG](/user/333855) 看似得在 $DO()$ 函数里截肢（）
里面 $for()$ 套 $for()$ 太多了。
by Meteor_ @ 2023-09-14 18:11:30
@[PwXmBjR_bYsVmG](/user/333855) 可能过不太去，反正不是卡常能卡过去的，复杂度差的有点多诶（）
by Meteor_ @ 2023-09-14 18:14:13
@[DELA](/user/822718) 没把。
by int233 @ 2023-09-14 18:19:19
@[Meteor_](/user/756594) e，我又加了一个剪枝，现在AC了。
by int233 @ 2023-09-14 18:22:49
@[PwXmBjR_bYsVmG](/user/333855) 啊？这么强
by Meteor_ @ 2023-09-14 18:36:38