有史以来做的思维量结合量最大的题。
给出的代码中实现了 Subtask6,7,9。
参考了出题人题解，这里强推：https://www.luogu.com.cn/article/4agpym8e。
Subtask5(k=1)
考虑设 c_i 表示第 i 个窗沿给下一个窗沿的雨水量，同时定 c_n=0，那么答案就是：
\sum \limits_{c}\prod_{i=1}^n (a_i-c_i+c_{i+1})
展开和式：
\sum \limits_{c} \sum \limits_{S \subseteq \{1,2,...,n\}} \prod \limits_{i\in S}(a_i-c_i)\prod_{i \not\in S}c_{i+1}
此时我们从左往右定 c_i 的值，f_{i,1} 表示包含了 i 的所有 S 的乘积的和，f_{i,0} 表示不包含 i 的所有 S 的乘积的和，来看一看所有情况的转移式：
-
i-1 \in S,i \not\in S$，贡献是 $\sum \limits_{0 \leq c_i \leq a_i}1=a_i+1
-
i-1 \not\in S,i \not\in S$，贡献是 $\sum \limits_{0\leq c_i \leq a_i}c_{i}=\frac{a_i(a_i+1)}{2}
-
i-1 \not\in S,i \in S$，贡献是 $ \sum \limits_{0\leq c_i \leq a_i}(a_i-c_i)c_i=\frac{a_i^2(a_{i}+1)}{2}-\frac{a_i (a_i+1)(2a_i+1)}{6}=\frac{(a_i-1)a_i(a_i+1)}{6}
-
i-1 \in S,i \in S$，贡献是 $\sum\limits_{0 \leq c_i \leq a_i}(a_i -c_i)=\frac{a_i(a_i+1)}{2}
有了以上推导的贡献，我们就可以对应的从 f_{i-1,0/1}\rightarrow f_{i,0/1} 了，时间复杂度 O(n)。
到这里我已经觉得非常妙了，甚至可以单独出一道题。不过别急，还有更高级的在后面。
Subtask6(k=n-1)
为了方便，我们不妨设 c_{i,j} 表示从第 i 个窗沿到第 i+j 个窗沿的雨水量。特别的，c_{i,0} 表示留下来的雨水数量。那么答案就是：
\sum\limits_c \prod \limits_{i=1}^n(\sum\limits_{j=0}^{\min (i-1,k)}c_{i-j,j})
这一步更妙，在 Subtask5 中的展开中，我们将 c_i 所造成的贡献集中在一起。我们此时也可以这样做，但是一步不好想通顺。不妨设 S_k 表示在上面的 \sum \limits_j 中选择了 i-j=k 的 j 的集合，同时将 c 合法的条件加上，那么原式就可以表示为(S_i 合法条件未标出)：
\sum \limits_c \prod \limits _{i=1}^n[c_{i,j}=a_i]\sum \limits_{j \in S_i}c_{i,j}
接下来我们来看如何抽丝剥茧地解决这个问题：
同样利用 dp 转移，但是这里 c,S 都有条件，c_{i,j} 的条件是和为定值，S_i 我们可以看作是 j 可以给 i=j,j-1,...,\max(1,j-k) 中的一个 S_i 贡献 1 ，不妨将这个分配的过程看作 i 从 i,i+1,...,\min(n,i+k) 中取贡献，同时每个数只能被取一次，由于 k=n-1，我们从 n 到 1 dp，记录该后缀中有多少个没有被选。
同时我们发现式子中 S_i 的贡献只和他的大小有关系，转移的时候不妨枚举 |S_i|，然后算方案数。
设当前有 r_i=\min(n-i,k)+1 个 c_{i,j} 可以取非 0，我们首先定好 S_i 具体为哪些下标，这是一个组合数的形式，然后我们不妨用这样一个模型来描述这个问题：
有 r_i 个盒子，其中有 |S_i| 个已经确定的盒子，放了 x 个球会贡献 x(我们称作第一种盒子)，其他盒子无论放了几个球贡献都是 1(我们称作第二种盒子)，一个方案的贡献各个盒子的贡献的积，求往这 r_i 个盒子中放 a_i 个没有区别的球的贡献之和。
不妨用生成函数表示每一个盒子，第一种盒子的生成函数是 \sum \limits_{i=0} ix^i=\frac{x}{(1-x)^2}，第二种是 \sum \limits _ix_i=\frac{1}{1-x}，那么结果为 [x^{a_i}](\frac{x}{(1-x)^2})^{|S_i|}\frac{1}{(1-x)^{r_i-|S_i|}}=[x^{a_i}]\frac{x^{|S_i|}}{(1-x)^{r_i+|S_i|}}，不妨用组合意义：将 a_i-|S_i| 个无差别球分到 r_i+|S_i| 个可空盒子里的方案数，那么方案就是 \binom{a_i+r_i-1}{|S_i|+r_i-1}，注意到这个组合数可以预处理。
那么我们就可以做到 O(n^3) 的时间复杂度了。
Subtask7(k \leq 16)
此时一定是要状态压缩了，设 f_{i,s} 表示 i,i+1,i+2,...,\min(i+k,n) 是否被使用，直接实现是 O(n3^k)，无法通过。
我们考虑到转移时能转移到 S 的 T 必须满足 T \subseteq S，而贡献只和集合大小有关，我们不妨设 g_{i,j,S} 表示 \sum \limits_{T\subseteq S,|T|=j}f_{i,T}，即做高维前缀和。用 g 辅助转移即可。
时间复杂度 O(nk^22^k) 了。
Subtask9
我们用 `Subtask6 ` 的做法，但是如何保证一个下标一定贡献到了 $[1,i-k)$ 之外的区间呢？只需要在 $i-k-1$ 的时候把他放到 `dp` 的第二维即可。此时时间复杂度是 $O(n^32^{n-k})$。
与 `Subtask7` 做法结合可以做到 $O(n^32^{\frac{n}{2}})$ 的优秀时间复杂度。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define p 998244353
#define ll long long
#define pc(x) __builtin_popcount(x)
ll inv[100],C[100][100],coe[100][100];
inline ll Binom(int n,int m){
ll ans=1;
for(int i=n-m+1;i<=n;i++)ans=ans*i%p;
for(int i=1;i<=m;i++)ans=ans*inv[i]%p;
return ans;
}
void init(){
inv[0]=inv[1]=1;for(int i=2;i<=90;i++)inv[i]=inv[p%i]*(p-p/i)%p;
for(int i=0;i<=90;i++){C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;}
}
int n,k;
int a[40];
namespace Subtask6{
ll f[40][40];
void solve(){
f[n+1][0]=1;
for(int i=n;i;i--)
for(int j=0;j<=n-i+1;j++)
for(int k=max(j-1,0);k<=n-i;k++)
(f[i][j]+=f[i+1][k]*C[k+1][j]%p*coe[i][k+1-j]%p)%=p;
printf("%lld\n",f[1][0]);
}
}
namespace Subtask7{
ll f[40][1<<18],g[20][1<<18];
void solve(){
f[n+1][(1<<k+1)-1]=1;
for(int i=n;i;i--){
for(int ss=0;ss<1<<k;ss++)for(int K=0;K<=k;K++){int s=(ss|1<<k);g[K][s]=0;}
for(int ss=0;ss<1<<k;ss++){int s=(ss|1<<k);g[pc(s)][s]=f[i+1][s];}
for(int K=0;K<=k;K++)for(int j=0;j<k;j++)for(int s=0;s<1<<k;s++)if(s>>j&1)(g[K][s|(1<<k)]+=g[K][s^(1<<j)|(1<<k)])%=p;
for(int ss=0;ss<1<<k;ss++){
int s=(ss|(1<<k));
for(int j=0;j<=pc(s);j++)//枚举 t 的位数
(f[i][s]+=g[j+1][(s>>1)|(1<<k)]*coe[i][pc(s)-j]%p)%=p;
}
}
printf("%lld",f[1][(1<<k+1)-1]);
}
}
namespace Subtask9{
int f[40][40];
void solve(){
ll ans=0;
for(int s=0;s<1<<(n-k-1);s++){//1 必须超出
memset(f,0,sizeof(f));
f[n+1][0]=1;int lim=0;
for(int i=n;i;i--){
int t=0;
if(i>k+1)t+=!(s>>(i-k-2)&1);
else ++t;
if(i+k<n)t+=(s>>(i-1)&1);
for(int j=0;j<=lim+t;j++)
for(int k=max(0,j-t);k<=lim;k++)
(f[i][j]+=f[i+1][k]*C[k+t][j]%p*coe[i][k+t-j]%p)%=p;
lim+=t;
}
if(pc(s)&1)(ans+=p-f[1][0])%=p;
else (ans+=f[1][0])%=p;
}
printf("%lld\n",ans);
}
}
int main(){
init();
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int r=min(n-i,k)+1;
for(int j=0;j<=min(r,a[i]);j++)coe[i][j]=Binom(a[i]+r-1,j+r-1);
}
if(k==0){
ll ans=1;
for(int i=1;i<=n;i++)ans=ans*a[i]%p;
return printf("%lld",ans),0;
}
else if(k==n-1)Subtask6::solve();
else if(k<=n/2)Subtask7::solve();
else Subtask9::solve();
}
```