题目概述

有一个序列 $\{a_n\}$ ，定义一次操作 $[L,R]$ 表示将 $[L,R]$ 中的数改成 $[L,R]$ 中的最大数。现在要进行 $q$ 轮，每轮随机一个区间 $[L,R]$ 进行操作，求出每个位置上最后数的期望。

解题报告

神仙DP题，我只会 $O(n^53^nq)$ ，加上玄学优化只能过 $n=8$ ……

根据期望的线性性，我们可以枚举 $i,j$ 表示 $i$ 这个位置最后变成第 $j$ 小的数的方案数，然后贡献就是方案数乘上 $a_j$ 。于是会想到这样的状态 $f_{i,x,L,R}$ 表示第 $i$ 轮 $[L,R]$ 变成第 $x$ 小的数的方案数，但是很明显这样无法存下所有状态，而且还会重复，所以是假的。

Orz劼司机，我们可以简单容斥一下：求出 $\le j​$ 的答案，那么减去 $\le j-1​$ 的答案就是 $=j​$ 的答案，所以我们可以定义 $f_{i,x,L,R}​$ 表示第 $i​$ 轮 $[L,R]​$ 变成 $\le​$ 第 $x​$ 小的数的方案数，同时 $L-1​$ 和 $R+1​$ 均 $>​$ 第 $x​$ 小的数，这样状态就是唯一的，并且隔开了外界，就可以转移了。

转移有三种：

1. 这次操作不影响 $[L,R]$ ，即要么在外面操作，要么在内部操作：

   $f_{i,x,L,R}\leftarrow f_{i-1,x,L,R}({(L-1)L\over 2}+{(R-L+1)(R-L+2)\over 2}+{(n-R)(n-R+1)\over 2})$

2. 枚举上一次的状态 $[l,R],l<L$ ，那么可以通过操作左端点在 $[1,l-1]$ ，右端点在 $L-1$ 来转移：

   $f_{i,x,L,R}\leftarrow f_{i-1,x,l,R}(l-1)$

3. 枚举上一次的状态 $[L,r],r>R$ ，那么可以通过操作左端点在 $R+1$ ，右端点在 $[r+1,n]$ 来转移：

   $f_{i,x,L,R}\leftarrow f_{i-1,x,L,r}(n-r)$

然后定义 $g_{i,j}$ 表示 $i$ 这个位置变成 $\le$ 第 $j$ 小的数的方案数，则：$g_{i,j}\leftarrow f_{q,j,L,R}(i\in[L,R])$ 。

考虑初始状态，我们枚举 $i$ 表示这次最大的数，然后往左往右找到 $i$ 的控制区间 $[L,R]$ ，做这个区间的DP。

我们发现后面两个转移都可以前缀和优化，所以这样是 $O(n^3q)$ 的……爆炸了？！

不过数是随机的……所以跑不满，可以过……

最后要注意到 $g_{i,j}$ 是不连续的，所以不能用 $g_{i,j}-g_{i,j-1}$ 来算，要记录上一次存在的 $g_{i,j}$ 。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=400,MOD=1e9+7;

int n,m,ID[maxn+5],a[maxn+5],rk[maxn+5],s[maxn+5][maxn];
LL f[2][maxn+5][maxn+5],g[maxn+5][maxn+5];

inline bool cmp(const int &A,const int &B) {return a[A]<a[B];}
#define Seg(x) ((LL)(x)*((x)+1)>>1)
inline void Solve(int L,int R,int rk){
    for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) f[0][i][j]=0;
    for (int t=f[0][L][R]=1,c=1;t<=m;t++,c^=1){
        LL (*F)[maxn+5]=f[c],(*G)[maxn+5]=f[c^1],sum;
        for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) F[i][j]=G[i][j]*s[i][j];
        for (int j=(sum=0,L);j<=R;j++,sum=0)
            for (int i=L;i<=j;i++) F[i][j]+=sum,sum+=G[i][j]*(i-1);
        for (int i=(sum=0,L);i<=R;i++,sum=0)
            for (int j=R;j>=i;j--) F[i][j]+=sum,sum+=G[i][j]*(n-j);
        for (int i=L;i<=R;i++) for (int j=i;j<=R;j++) F[i][j]%=MOD;
    }
    for (int i=L;i<=R;i++)
        for (int j=L;j<=i;j++)
            for (int k=i;k<=R;k++)
                g[i][rk]=(g[i][rk]+f[m&1][j][k])%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),ID[i]=i;
    a[0]=a[n+1]=2e9;sort(ID+1,ID+1+n,cmp);for (int i=1;i<=n;i++) rk[ID[i]]=i;
    for (int i=1;i<=n;i++) for (int j=i;j<=n;j++) s[i][j]=(Seg(i-1)+Seg(j-i+1)+Seg(n-j))%MOD;
    for (int i=1,L,R;i<=n;i++) {for (L=i;a[L-1]<=a[i];L--);for (R=i;a[R+1]<=a[i];R++);Solve(L,R,rk[i]);}
    for (int i=1,ans=0;i<=n;i++,ans=0){
        for (int j=1,lst=0;j<=n;j++)
            if (g[i][j]) ans=(ans+(LL)(g[i][j]+MOD-lst)*a[ID[j]]%MOD)%MOD,lst=g[i][j];
        printf("%d",ans);i<n?putchar(' '):puts("");
    }return 0;
}