P7512 「Byakkai OI 2021」Eaquira

给定 $n$，并在数轴上截取 $[1,n]$ 的整点。 定义**极长连续黑区间段**为满足 $1 \le L \le R \le p$ 的区间段 $[L,R]$，且编号在 $[L,R]$ 内的区间都是黑色，且其不能再扩展，即编号为 $L-1$（如果存在，下同）和 $R+1$ 的区间都是白色。 首先，请您将它们划分成若干个区间 $[l_1,r_1],[l_2,r_2],\dots,[l_p,r_p]$，满足 $l_1=1,r_p = n$，且对于 $1 \le i < p$ 有 $r_i = l_{i+1}-1$；对于 $1 \le i \le p$ 满足 $l_i \le r_i$。 其二，您需要将每个区间标记为黑色或是白色，但不允许第 $1$ 个区间和第 $p$ 个区间同时被标记为黑色。 其三，请您在每个区间内选出一个子区间，称为**绝妙子区间**。 其四，请您在每个极长连续黑区间段中各选出一个黑色区间，称为**绝妙黑区间**。 其五，在所有的极长连续黑区间段中钦定若干个称作**绝妙极长连续黑区间段**。 定义一种以上述步骤所确定的方案的权值为黑色区间的个数与绝妙极长连续黑区间段个数的和。 我本来希望您求出对于 $s = 0,1,2,\dots,n$ 得到可以使得最终权值为 $s$ 的方案数。不过我也准备了一些更低要求的挑战。详见输入格式。 答案对 $998244353$ 取模。

一行，两个整数 $n,{\rm type}$。 若 ${\rm type} = 0$，则表示需要对 $0 \le s \le n$ 求出权值为 $s$ 的方案数。 若 ${\rm type} = 1$，则表示需要求出对所有 $0 \le s \le n$ 的总方案数。

若 ${\rm type} = 0$，则一行 $n+1$ 个非负整数，依次表示对于 $s = 0,1,2,\dots,n$ 的答案。 若 ${\rm type} = 1$，则一行一个非负整数，表示答案。

**样例解释** 以下用 $0$ 表示黑，$1$ 表示白。 对于第一个样例，考虑 $[1,3]$ 的 $4$ 种划分： - $[1,1],[2,2],[3,3]$： 此时选出无序数对的方案数为 $1$。 考虑每个区间的黑白标记情况，有如下 $4$ 种方案： - $001,100$：此时可以选择将唯一的极长连续黑区间段标记为绝妙与否，则权值为 $2$ 或 $3$，选择绝妙黑区间的方案数为 $2$。 - $101$：此时可以选择将唯一的极长连续黑区间段标记为绝妙与否，则权值为 $1$ 或 $2$，选择绝妙黑区间的方案数为 $1$。 - $[1,2],[3,3]$ 或 $[1,1],[2,3]$： 此时选出无序数对的方案数为 $3$。 考虑每个区间的黑白标记情况，有如下 $2$ 种方案： - $01,10$：此时可以选择将唯一的极长连续黑区间段标记为绝妙与否，则权值为 $1$ 或 $2$，选择绝妙黑区间的方案数为 $1$。 - $[1,3]$： 此时选出无序数对的方案数为 $6$。 考虑每个区间的黑白标记情况，有如下 $1$ 种方案： - $1$：此时权值为 $0$，总方案数为 $6$，选择绝妙黑区间的方案数为 $1$。 故权值为 $0$ 的方案数为 $6 \times 1 = 6$，权值为 $1$ 的方案数为 $1 \times 1 + 2 \times 3 \times 2 \times 1 = 13$，权值为 $2$ 的方案数为 $1 \times 2 \times 2 + 1 \times 1 + 2 \times 3 \times 2 \times 1 = 17$，权值为 $3$ 的方案数为 $1 \times 2 \times 2 = 4$。 对于第二个样例，不予解释。 **数据范围** **本题使用捆绑测试。** 具体子任务限制及分值如下表： |子任务编号|分值|$n \le $|${\rm type} =$|时限 / s| |:-:|:-:|:-:|:-:|:-:| |$0$|$1$|$8$|$0$|$1$| |$1$|$4$|$13$|$1$|$1$| |$2$|$8$|$300$|$1$|$1$| |$3$|$5$|$70$|$0$|$1$| |$4$|$10$|$5 \times 10^3$|$1$|$1$| |$5$|$8$|$300$|$0$|$1$| |$6$|$12$|$2 \times 10^5$|$1$|$1$| |$7$|$22$|$10^3$|$0$|$2$| |$8$|$30$|$2 \times 10^5$|$0$|$2.5$| 对于所有数据，$1 \le n \le 2 \times 10^5$，${\rm type} \in \{0,1\}$。