一个长度为 $n$ 的不确定序列，每个数在 $[1,n]$ 之间。给出 $m$ ，求所有序列的 $prod_{i=1}^{n-m+1}w[ ext{Max}_{j=i}^{j+m-1}a[j]]$ 的总和，即对所有序列求每个长度为 $m$ 的子区间的最大值乘积之和。答案对 $998244353$ 取模。
$mle nle 400$ 。
题解
dp
设 $f[i][j]$ 表示长度为 $i$ 的序列，每个数都在 $[1,j]$ 之间的所有序列每个长度为 $m$ 的子区间最大值乘积之和。
那么如果这个序列没有出现过 $j$ ，则有 $f[i][j]=f[i][j-1]$ 。
如果这个序列出现过 $j$ ，那么考虑枚举 $j$ 从左到右第一个出现的位置 $k$ ，所有包含 $k$ 的区间最大值都为 $j$ 。令包含 $k$ 的长度为 $m$ 的子区间个数为 $c$ ，则 $k$ 的贡献为 $v[j]^c$ 。左面没有出现过 $j$ ，贡献为 $f[k-1][j-1]$ ；右面可能还会出现 $j$ ，贡献为 $f[i-k][j]$ 。
故总的dp方程为：$f[i][j]=sumlimits_{k=1}^iv[j]^{c[i][k]}·f[k-1][j-1]·f[i-k][j]$ ，其中 $c[i][k]$ 表示长度为 $i$ 的区间的所有长度为 $m$ 的子区间中包含位置 $k$ 的个数，可以预处理出来也可以分类讨论。
答案为 $f[n][n]$ 。
注意边界问题：当区间长度 $i$ 小于 $m$ 时，贡献就是 $序列个数 imes 1=j^i$ 。
预处理幂次，时间复杂度 $O(n^3)$
#include <cstdio>
#include <algorithm>
#define N 410
#define mod 998244353
using namespace std;
typedef long long ll;
ll w[N] , p[N][N] , c[N][N] , f[N][N];
int main()
{
int n , m , i , j , k;
scanf("%d%d" , &n , &m);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%lld" , &w[i]) , p[i][0] = 1;
for(j = 1 ; j <= n ; j ++ )
p[i][j] = p[i][j - 1] * w[i] % mod;
}
for(i = 0 ; i <= n ; i ++ ) f[0][i] = 1;
for(i = 1 ; i < m ; i ++ )
for(j = 0 ; j <= n ; j ++ )
f[i][j] = f[i - 1][j] * j % mod;
for(i = m ; i <= n ; i ++ )
for(j = 1 ; j <= i - m + 1 ; j ++ )
for(k = j ; k < j + m ; k ++ )
c[i][k] ++ ;
for(i = m ; i <= n ; i ++ )
{
for(j = 1 ; j <= n ; j ++ )
{
f[i][j] = f[i][j - 1];
for(k = 1 ; k <= i ; k ++ )
f[i][j] = (f[i][j] + f[k - 1][j - 1] * f[i - k][j] % mod * p[j][c[i][k]]) % mod;
}
}
printf("%lld
" , f[n][n]);
return 0;
}