题目回顾

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，进行 $q$ 次操作，每次操作等概率随机选择一个区间 $[l, r]$（共有 $T = \frac{n(n+1)}{2}$ 种可能），将该区间内所有数改成该区间的最大值。 求 $q$ 次操作后每个位置 $i$ 的期望值，并输出：

$E(a_i) \times T^q \bmod (10^9+7)$

算法思路

这个问题如果直接模拟所有可能的操作序列，复杂度太高。 代码采用了 动态规划 + 二维前缀和 的方法，直接计算每个区间在 $q$ 次操作后的期望和（已乘 $T^q$）。

状态定义

设$f_{t}[l][r]$ = 经过 $t$ 次操作后，区间 $[l,r]$ 内所有数都变成该区间原来的最大值时，这个值的和（乘 $T^t$） 注意这里 "和" 是指所有可能操作序列下该区间最大值的总和（不是期望，已经乘了 $T^t$）。

初始时： $f_0[l][r] = \max_{l \le k \le r} a_k$ 因为 $0$ 次操作时，区间 $[l,r]$ 的最大值就是它本身的最大值，并且只有 $1$ 种操作序列（不操作），所以乘 $T^0 = 1$ 后就是它本身。

状态转移

考虑从 $f_{t-1}$ 转移到 $f_t$。

一次操作中，我们随机选择一个区间 $[L,R]$，考虑它对区间 $[l,r]$ 的影响：

1. $[L,R]$ 与 $[l,r]$ 相交但不完全包含 $[l,r]$

代码中将这种情况分为三类：

$L < l$ 且 $r \le R \le n$（左包含）

贡献为：$\sum_{L=1}^{l-1} \sum_{R=r}^{n} f_{t-1}[L][R] \times (r-l+1)$ 代码中对应：Sum(1, l - 1, r, r) * (r - l + 1)

$l \le L \le r$ 且 $R > r$（右包含）

贡献为：$\sum_{L=l}^{l} \sum_{R=r+1}^{n} f_{t-1}[L][R] \times (r-l+1)$ 代码中对应：Sum(l, l, r + 1, n) * (r - l + 1)

$L < l$ 且 $R > r$（完全包含但 $L \ne l$ 或 $R \ne r$）

贡献为：$\sum_{L=1}^{l-1} \sum_{R=r+1}^{n} f_{t-1}[L][R]$ 代码中对应：Sum(1, l - 1, r + 1, n)

2. $[L,R]$ 完全等于 $[l,r]$ 或不相交

完全等于 $[l,r]$

区间数：$1$ 贡献：$f_{t-1}[l][r] \times 1$

与 $[l,r]$ 不相交

区间数：$\frac{(l-1)l}{2} + \frac{(n-r)(n-r+1)}{2}$ 贡献：$f_{t-1}[l][r] \times \left( \text{Val}(l-1) + \text{Val}(n-r) \right)$

在 $[l,r]$ 内部（但不等于 $[l,r]$）

区间数：$\frac{(r-l+1)(r-l)}{2}$ 贡献：$f_{t-1}[l][r] \times \text{Val}(r-l)$

这三部分合并为： $f_{t-1}[l][r] \times \left( \text{Val}(r-l+1) + \text{Val}(l-1) + \text{Val}(n-r) \right)$

复杂度分析

空间复杂度：$O(n^2)$（使用滚动数组）

时间复杂度：$O(q \cdot n^2)$

对于 $n \le 400$，$q \le 400$ 可以接受

最终输出

最终只需要输出每个位置 $i$ 的值，即 $f_q[i][i]$，因为单个位置 $i$ 可以看作区间 $[i,i]$。

总结

这道题通过巧妙的 DP 设计，将随机操作的影响转化为对区间最大值的统计，利用二维前缀和优化转移，避免了直接枚举所有可能的操作序列，在多项式时间内解决了问题。