题目链接：
http://www.lydsy.com/JudgeOnline/problem.php?id=4574
考虑数字随机并且值域够大，我们将元素离散化并且不需要去重。
令$g[i]$表示每一个位置的期望大小。
那么${Ans=\sum (g[i]*(\frac{n(n+1))}{2})^{q})}$
考虑根据这个${(\frac{n(n+1))}{2})^{q}}$转换一下问题，是不是可以变成：
---------------------------------------------分割线----------------------------------------------------------------
令${sum[i][j]}$表示序列的第$i$个位置的元素在$q$次操作后变成了离散化之后$j$大的方案数。
那么${Ans=\sum_{i=1}^{n}\sum _{j=1}^{n}(sum[i][j]*X[j])}$ //$X[i]$表示第离散化之后的第$i$个元素原本对应的数字的大小。
---------------------------------------------分割线----------------------------------------------------------------
考虑如何求${sum}$数组。
从左至右枚举离散化数列每一位上的值(设我枚举的数字为第${E}$大),我们知道一个数至多能够影响到一个有限的区间,即区间${[L,R]}$中每一个数字都没有它大。
令${DP[k][i][j]}$表示第$k$次操作之后区间${[i,j]}$的值都小于等于当前枚举值的方案数。
转移:
${DP[k][i][j]=\sum _{u=L}^{i-1}(DP[k-1][u][j]*(u-1))+\sum _{v=j+1}^{R}(DP[k-1][i][v]*(n-v))+DP[k-1][i][j]*(cnt[i-1]+cnt[j-i+1]+cnt[n-j])}$
那么为啥是这样呢?
我来尝试解释一下第一项即${\sum _{u=L}^{i-1}(DP[k-1][u][j]*(u-1))}$![【UOJ#196】【BZOJ4574】[Zjoi2016]线段树](https://image.shishitao.com:8440/aHR0cHM6Ly9iYnNtYXguaWthZmFuLmNvbS9zdGF0aWMvTDNCeWIzaDVMMmgwZEhCekwybHRZV2RsY3pJd01UVXVZMjVpYkc5bmN5NWpiMjB2WW14dlp5ODVNVGsxTWpBdk1qQXhOekF5THpreE9UVXlNQzB5TURFM01ESXlOekl3TVRjd05UUTNNQzB4TmpReU9ERTJNRE13TG5CdVp3PT0uanBn.jpg?w=700&webp=1 "【UOJ#196】【BZOJ4574】[Zjoi2016]线段树")
这个转移其实是从区间${[U,j]}$转移到区间${[i,j]}$，拿为啥要乘上一个系数$(u-1)$,是因为我要使得${[u,i-1]}$这段区间内不再小于等于当前枚举的值。所以只要选取了${[1,u-1]}$这段区间内的一个元素作为操作的左端点，固定右端点为${i-1}$则一定会存在一个数字(因为第${L-1}$个数一定大于当前枚举的数)使得${[u,i-1]}$这个区间的数不再小于等于当前枚举的数。
第二项的理解和第一项基本相同。
第三项就比较简单了，如果我选取的区间不跨过第$i$个位置或第$j$个位置，那就不会产生状态的改变，可与之间从区间${[i,j]}$向区间${[i,j]}$转移
对于每一个枚举的数字就算出了$DP$数组，我为了方便统计答案再设一个数组${sum{}'}$表示序列的第$i$个位置的元素在$q$次操作后变成了离散化之后数小于等于$j$大数的方案数。
${sum{}'[i][E]=sum{}'[i][E]+\sum _{u=L}^{R-1}\sum _{v=u+1}^{R}DP[q][u][v]}$
最后在利用${sum{}'}$数组计算出${sum}$数组。
${Ans=\sum_{i=1}^{n}\sum _{j=1}^{n}(sum[i][j]*X[j])}$
参考:http://blog.csdn.net/qq_34637390/article/details/51290087
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 410
#define llg long long
#define md (llg)((1e9)+7)
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
#define DD(i,j,k) dp[(i)%2][j][k]//方便滚动数组优化空间
llg n,m,q,x[maxn],rank[maxn],L,R,wz[maxn];
llg cnt[maxn],dp[][maxn][maxn],sum[maxn][maxn],A[maxn][maxn]; inline bool cmp(llg a,llg b) {return x[a]<x[b];} void init()
{
cin>>n>>q;
for (llg i=;i<=n;i++) scanf("%lld",&x[i]);
for (llg i=;i<=n;i++) wz[i]=i;
sort(wz+,wz+n+,cmp);
for (llg i=;i<=n;i++) rank[wz[i]]=i;//第i个元素是第rank[i]小的
//离散化
for (llg i=;i<=n;i++) cnt[i]=(i*i+i)/;
for(int i=;i<=n;i++)for(int j=i;j<=n;j++)A[i][j]=cnt[i-]+cnt[n-j]+cnt[j-i+];
} void DP(llg now)
{
for (llg i=L;i<=R;i++) for (llg j=L;j<=R;j++) DD(,i,j)=DD(,i,j)=;
DD(,L,R)=;
llg val;
for (llg k=;k<=q;k++)
{
for (llg i=L;i<=R;i++)
{
val=;
for(int j=R;j>=i;j--)
{
DD(k,i,j)=val; val=(val+DD(k-,i,j)*(n-j))%md;//计算第二项
}
}
for (llg j=L;j<=R;j++)
{
val=;
for(llg i=L;i<=j;i++)
{
DD(k,i,j)=(DD(k,i,j)+val)%md; val=(val+DD(k-,i,j)*(i-));//计算第一项
}
}
for (llg i=L;i<=R;i++)
{
for (llg j=i;j<=R;j++)
{
DD(k,i,j)=(DD(k,i,j)+(DD(k-,i,j)*A[i][j]))%md;//计算第三项
}
}
}
for (llg i=L;i<=R;i++)
{
val=;
for (llg j=R;j>=i;j--)
{
val+=DD(q,i,j); val%=md;
sum[j][rank[now]]+=val;
sum[j][rank[now]]%=md;
}
}
} int main()
{
//yyj("seg");
init();
for (llg i=;i<=n;i++)
{
L=R=i;
while (L && x[L]<=x[i]) L--; L++;
while (R<=n && x[R]<=x[i]) R++; R--;
//预处理第i个元素可以影响的区间
DP(i);
} llg ans=;
for (llg i=;i<=n;i++)
{
ans=;
for (llg j=;j<=n;j++)
{
if (sum[i][j]==) continue;
for (llg k=;k<j;k++) sum[i][j]-=sum[i][k];
while (sum[i][j]<) sum[i][j]+=md;
ans+=x[wz[j]]*sum[i][j]; ans%=md;
}
while (ans<) ans+=md;
printf("%lld",ans);
if (i!=) printf(" ");
}
return ;
}