考虑直接顺着从\(1\)填数填到\(n\)发现这是在胡扯

所以考虑一些奇诡的东西，譬如最后的答案长什么样子

显然某一种方案的贡献是一个\(\prod_{i=1}^nw_i^{t_i}\)状物，\(t_i\)表示\(i\)在多少个长度为\(m\)的区间里为最大值

而这里又是最大值，所以可以考虑从大到小填数，每次把填完之后相应的分裂区间，同时在这个时候也可以计算一些贡献

于是我们设\(f_{l,r,k}\)表示对于区间\([l,r]\)最大值为\(k\)，我们枚举这个最大值最后一次出现的位置，同时跨过这个位置长度为\(m\)的区间的最大值肯定是\(k\)了，于是我们在这里就可以计算出\(w_k\)的贡献

于是有

\[f_{l,r,k}=\sum_{i=l}^{r}w_k^{calc(r-l+1,i)}\sum_{j=1}^kf_{l,i-1,j}\times \sum_{j=1}^{k-1}f_{i+1,r,j}\]

其中\(calc(r-l+1,i)\)表示对于一个长度为\(r-l+1\)的序列，有多少个长度为\(m\)的区间跨过\(i\)位置

发现这里能维护前缀和就能快速转移了

答案就是\(\sum_{i=1}^nf_{1,n,i}\)

同时我们发现这里维护区间太奢侈了，只要有一个区间长度我们就能转移了，所以我们直接改为维护区间长度

状态数\(n^2\)，转移复杂度\(O(n)\)，复杂度为\(O(n^3)\)

代码

#include
    
     #define re register#define LL long longconst int mod=998244353;const int maxn=403;int n,m,w[maxn];int dp[maxn][maxn],vis[maxn][maxn],a[maxn][maxn],b[maxn][maxn];inline int ksm(int a,int b) {    int S=1;    for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;    return S;}int f(int l,int k) {    if(!l) return 1;    if(!k) return 0;    if(vis[l][k]) return dp[l][k];    if(l
     
      1) dp[l][k]=f(l,k-1);    for(re int i=0;i