RT

$O(qn^3)$ 的做法，复杂度不受到随机影响，目前#7已从 $2.91s$ 卡到 $1.25s$

也问一下有没有希望过。

代码：

#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];
	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];
		}
	}
	for(ll j=0;j<=n+1;j++){
		for(ll k=j+2;k<=n+1;k++){
			f[0][j][k]=0;
		}
	}
	ll cnt=0,kk=0;
	for(ll i=1;i<=n;i++){
		if(R[i]>=L[i]+2){
			f[0][L[i]][R[i]]=1;
			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 i=1;i<=q;i++){
		for(ll j=1;j<=n+1;j++){
			for(ll k=j+2;k<=n+1;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=n+1;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<=n+1;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<=n+1;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=n+1;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;
}