{"problem":{"name":"「GLR-R3」清明","description":{"content":"雨打在窗沿，下坠，一级一级。 这里一共有 $n$ 级窗沿，从高到低编号，最高层编号为 $1$，最底层编号为 $n$。假设在某一瞬间，第 $i$ 级窗沿上有 $a_i$ 单位体积的雨水。由于奇妙的物理原因，第 $i$ 级的雨水将在「下一个瞬间」滴向第 $i+1,i+2,\\dots,\\min\\{i+k,n\\}$ 级，也可能留在第 $i$ 级，但是每一种去向的雨水的单位体积都应是非负整数，且总和为 $","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8478"},"statements":[{"statement_type":"Markdown","content":"雨打在窗沿，下坠，一级一级。\n\n这里一共有 $n$ 级窗沿，从高到低编号，最高层编号为 $1$，最底层编号为 $n$。假设在某一瞬间，第 $i$ 级窗沿上有 $a_i$ 单位体积的雨水。由于奇妙的物理原因，第 $i$ 级的雨水将在「下一个瞬间」滴向第 $i+1,i+2,\\dots,\\min\\{i+k,n\\}$ 级，也可能留在第 $i$ 级，但是每一种去向的雨水的单位体积都应是非负整数，且总和为 $a_i$。\n\n设在「下一个瞬间」，第 $i$ 级窗沿上有 $a_i'$ 单位的雨水，那么称此时雨水的**奇妙度**为 $\\prod_{i=1}^n a_i'$。现在，悲伤的人儿想知道，对于所有**本质不同的**「下一个瞬间」，雨水的奇妙度之和对素数 $P=998244353$ 取模的结果。\n\n两个「下一个瞬间」本质不同，当且仅当存在编号 $i<j$ 的两级窗沿，从窗沿 $i$ 滴向窗沿 $j$ 的雨水的单位体积不同。\n\n## Input\n\n第一行输入两个正整数 $n,k$，分别表示窗沿的数量、限制雨点滴落距离的常数。\n\n第二行输入 $n$ 个非负整数 $a_1,a_2,a_3,\\cdots,a_n$，其中 $a_i$ 表示第 $i$ 级窗沿在这一瞬间的雨水体积。\n\n## Output\n\n输出一行一个整数，表示所有本质不同的「下一个瞬间」，雨水的奇妙度之和对 $P$ 取模后的结果。\n\n[samples]\n\n## Background\n\n&emsp;&emsp;「&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;，&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;&emsp;」\n\n---\n\n&emsp;&emsp;“你非说这不是我的实力，那凭什么一个偶然错音就不能毁了我的命运？！”\n\n&emsp;&emsp;天依没有注意到，心中所哭嚎向的那个人，同她一样撑着伞，身后十来步而已。\n\n---\n\n&emsp;&emsp;**清明**　「你在名为弱小的深渊　究竟看见过什么」\n\n## Note\n\n#### 样例 #1 解释\n\n容易发现总共只有一种本质不同的「下一个瞬间」，也就是每级窗沿都没有雨水向其他窗沿滴落。\n\n所以最终 $a'=\\{2,2,2\\}$，权值为 $8$。\n\n#### 样例 #2 解释\n\n设 $c_k$ 表示从第 $k$ 级窗沿滴向第 $k+1$ 级窗沿的雨点体积，显然有 $c_3=0$。\n\n枚举所有合法的滴落情况：\n\n- $c=\\{0,0,0\\},b=\\{2,2,2\\}$，权值为 $8$；\n- $c=\\{0,1,0\\},b=\\{2,1,3\\}$，权值为 $6$；\n- $c=\\{0,2,0\\},b=\\{2,0,4\\}$，权值为 $0$；\n- $c=\\{1,0,0\\},b=\\{1,3,2\\}$，权值为 $6$；\n- $c=\\{1,1,0\\},b=\\{1,2,3\\}$，权值为 $6$；\n- $c=\\{1,2,0\\},b=\\{1,1,4\\}$，权值为 $4$；\n- $c_1=2$，此时必然有 $b_1=0$，此情况下的三种方案权值均为 $0$；\n\n所以所有本质不同的「下一个瞬间」的权值和为 $8+6+0+6+6+4+0+0+0=30$。\n\n### 数据规模与约定\n\n**本题采用 Subtask 的计分方式。**\n\n对于 $100\\%$ 的数据，$0\\le k<n\\le 32$，$0\\le a_i<P$。\n\n对于不同的子任务，作如下约定：\n\n| 子任务编号 |   $n$   |   $k$   | $\\max a_i$ | 子任务分值 |\n| :--------: | :-----: | :-----: | :--------: | :--: |\n|    $1$     | $\\le32$ |  $<n$   |    $=0$    | $2$  |\n|    $2$     | $\\le32$ |  $=0$   |    $<P$    | $2$  |\n|    $3$     | $\\le32$ |  $<n$   |    $=1$    | $3$  |\n|    $4$     | $\\le5$  |  $<n$   |   $\\le4$   | $20$ |\n|    $5$     | $\\le32$ |  $=1$   |    $<P$    | $13$ |\n|    $6$     | $\\le32$ | $=n-1$  |    $<P$    | $10$ |\n|    $7$     | $\\le32$ | $\\le16$ |    $<P$    | $20$ |\n|    $8$     | $\\le25$ |  $<n$   |    $<P$    | $10$ |\n|    $9$     | $\\le32$ |  $<n$   |    $<P$    | $20$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8478","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["3 0\n2 2 2","8"],["3 1\n2 2 2","30"],["5 3\n2 3 4 4 3","275200"]],"created_at":"2026-03-03 11:09:25"}}