【题解】
这题的期望dp好神奇啊（可能是我太菜了）
由于每个位置都完全一样，所以我们设$f_{i,j}$表示审了连续$i$个位置，最大值不超过$j$的期望。
那么只要考虑最大值为$j$的期望，其他从$f_{i,j-1}$加进来即可。
枚举最大值第一次出现的位置$p$（如果位置编号为$[1,i]$的话，因为位置都等价，所以可以这样做）
然后考虑$p$一定对于这些区间有贡献$[\max(1, p-K+1), \min(i-K+1, p)]$，那么这些区间的价值都是$w_j$，乘起来即可。
然后前后两半互斥，分别转移即可。
设区间长度为$len$，也就是上面那坨减一下+1。
所以$f_{i,j} = f_{i,j-1} + \sum_{p=1}^i f_{p-1,j-1} * w_j^{len} * f_{i-p, j}$
考虑初始状态，连续$i$个位置最大值不超过$j$，其中$i < k$，也就是还没有组成一个完整的区间，那么根据上面的转移方程，这个区间的值完全由自己决定，也就是$f_{i,j} = j^i$。
复杂度$O(n^3)$
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>using namespace std;typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = + ;
const int mod = ;int n, K, w[M];
int f[M][M], c[M][M];
// 审了i套题，最大难度不超过j的方案数
// f[i, j] = f[i, j-1] + \sum_{x=1}^{i} f[x-1, j-1] * f[n-x, j] * w[x]^pinline int pwr(int a, int b) {
int ret = ;
while(b) {
if(b&) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return ret;
}int main() {
cin >> n >> K;
for (int i=; i<=n; ++i) {
scanf("%d", w+i);
c[i][] = ;
for (int j=; j<=n; ++j) c[i][j] = 1ll * c[i][j-] * w[i] % mod;
}
for (int i=; i<=n; ++i) f[][i] = ;
for (int i=; i<=n; ++i) {
for (int j=; j<=n; ++j) {
if(i < K) f[i][j] = pwr(j, i);
else {
f[i][j] = f[i][j-];
for (int x=; x<=i; ++x) {
f[i][j] = f[i][j] + 1ll * f[x-][j-] * f[i-x][j] % mod * c[j][min(i-K+, x) - max(x-K+, ) + ] % mod;
if(f[i][j] >= mod) f[i][j] -= mod;
}
}
}
}
cout << f[n][n]; return ;
}
