或许更好的阅读体验

首先观察题面，期望乘上 $(\frac{n(n + 1)}{2})^q$ ，即乘上所有可能的操作数。其实就是求所有可能的值乘上方案数。可以根据期望的定义感性理解一下。

所有我们不妨先把答案的式子写出来，即 $ans_i = \sum v_j \times h(i, v_j)$，其中 $h(i, v)$ 为第 $i$ 个数为 $v$ 的方案数。

然后考虑如何计算 $h(i, v)$，一个很经典的技巧就是用第 $i$ 个数小于等于 $v$ 的方案数减去小于等于 $v - 1$ 的方案数。

所以我们不妨继续尝试下 DP。容易发现 DP 的阶段应该是操作的次数，记为 $i$；同时为了满足上述计算，还要记录一个值 $v$。然后你会发现不能单独记录某一个数的值为 $v$，因为题目是区间操作，所以记录某个区间 $[l, r]$ 内的数全部小于等于 $v$。同时我们给出必要的限制，即 $a_{l - 1}$ 和 $a_{r + 1}$ 都必须大于 $v$。

到此，我们便顺利地得出状态表示 $f(i, v, l, r)$，其含义就是上文的叙述。

然后思考转移，这一步比较简单，我们直接给出转移式：

$$f(i, v, l, r) = f(i - 1, v, l, r) \times g(l, r) + \sum_{j > r} f(i - 1, v, l, j) + \sum_{j < l}f(i - 1, v, j, r)$$

其中 $g(l, r)$ 记录的是所有没有影响的操作。这些操作可以是对于 $[l, r]$ 内部区间修改成最大值，也可以是对于 $[1, l - 1]$ 和 $[r + 1, n]$ 的。

所以 $g(l, r) = \frac{(r - l + 1)(r - l + 2)}{2} + \frac{l(l + 1)}{2} + \frac{(n - r)(n - r + 1)}{2}$。

到此我们便得到了 $O(n^3q)$ 的做法，但是由于数据随机所以近似于 $O(n^2q)$ 就可以过了。

然而我们可以继续优化，注意到在 $f$ 的式子中上述式子中全程 $v$ 没有变化，所以我们不妨思考一下如何去掉这一维。

此时我们再把 $f$ 代入 $h$，可以得到 $h(i, v) = \sum_{i \in [l, r]} [f(q, v, l, r) - f(q, v - 1, l, r)]$，所以就有 $ans_i = \sum v_j \times \sum_{i \in [l, r]} [f(q, v_j, l, r) - f(q, v_j - 1, l, r)]$。

此时我们可以发现，对于某个 $f(q, v, l, r)$，它的贡献为 $f(q, v, l, r) * (v_j - v_{j + 1})$，因此我们可以直接带着 $(v_j - v_{j + 1})$ 的贡献做 DP，这样就只要记录 $f’(q, l, r)$ 就行了。

但这样子初值就不同了，考虑对于 $f’(0, l, r)$ 它要带有 $(v_1 - v_2 + v_2 - v_3 + …)$ 的贡献，我们会发现 $f’(0, l, r)$ 其实就是区间最大值减最小值，直接做就完了。

于是我们就优化到了 $O(n^2q)$，彻底拿下了这道题。具体实现时，由于这个题空间给的很小，还需要滚动数组优化下空间。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

const int N = 1010, Mod = 1e9 + 7;

int n, q;
int a[N], f[2][N][N], g[N][N], s1[2][N][N], s2[2][N][N];

int add(int a, int b, int c) {
    return ((a + b) % Mod + c) % Mod;
}
int mul(int a, int b) {
    return 1ll * a * b % Mod;
}
int calc(int x) {
    return 1ll * x * (x + 1) / 2;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    a[0] = a[n + 1] = 1e9 + 1;
    for (int l = 1; l <= n; l ++) {
        int maxx = 0;
        for (int r = l; r <= n; r ++) {
            maxx = max(maxx, a[r]);
            if (l == 1 && r == n) f[0][l][r] = maxx;
            else if (a[l - 1] > maxx && a[r + 1] > maxx)
                f[0][l][r] = (maxx - min(a[l - 1], a[r + 1]) + Mod) % Mod;
            g[l][r] = add(calc(r - l + 1), calc(l - 1), calc(n - r));
        }
    }
    for (int i = 1; i <= q; i ++) {
        int now = i & 1, pre = i & 1 ^ 1;
        for (int l = 1; l <= n; l ++) {
            for (int r = l; r <= n; r ++) 
                s1[pre][l][r] = (s1[pre][l - 1][r] + mul(f[pre][l][r], l - 1)) % Mod;
            for (int r = n; r >= l; r --)  
                s2[pre][l][r] = (s2[pre][l][r + 1] + mul(f[pre][l][r], n - r)) % Mod;
        }
        for (int l = 1; l <= n; l ++)
            for (int r = l; r <= n; r ++)           
                f[now][l][r] = add(mul(f[pre][l][r], g[l][r]), s1[pre][l - 1][r], s2[pre][l][r + 1]);
    }
    for (int i = 1; i <= n; i ++) {
        int ans = 0;
        for (int l = 1; l <= i; l ++)
            for (int r = i; r <= n; r ++)
                ans = (ans + f[q & 1][l][r]) % Mod;
        cout << ans << " ";
    }
    return 0;
}