P7720 「EZEC-10」「Byakkai OI 2021」Estahv

> chrisl gjeztor Amledza > prof ovelmizer > dos carm ammeidha alzenghar > kawy may noxial gjeztor > Rupieilla vas photreywz idha

我们有排成一排的无限个格子，它们从左往右以 $1,2,\dots$ 编号。 你可以在每个格子中填入任意**正整数** $k$，则你会得到 $C_k$ 的权值。 其中满足 $C_0=C_1=1$，$C_i = \sum\limits_{j=0}^{i-1} C_j C_{i-j-1}$ $(i \ge 2)$。 若干个格子的总权值定义为它们的权值之积。 现在你需要从左往右依次在格子中填入数字，直到填入的数字之和等于 $n$ 或超过 $n$ 为止。 如此之后，你还需要为每个填入数字的格子涂上黑色或者白色。需要满足：不存在任意连续的 $2$ 个及以上白色的格子，且第一个格子必须为黑色，最后一个填入数字的格子必须为白色。 然后，你需要把所有相邻的均填入了数字的同色格子两两连边，并从中选出一个格子集合 $S$，满足 $S$ 内的格子两两不连通（可以为空）。 一种方案的权值定义为所有格子的总权值。 给定 $n$，请你对于 $s=0,1,\dots,n$，计算所有完成以上操作，且填入的数字之和**恰好**为 $n$，且黑色的格子数为 $s$ 的所有方案的权值之和。 两种方案不同当且仅当填入数字的格子数不同或对应格子填入的数字不同或对应格子颜色不同或 $S$ 集合不同。 对 $998244353$ 取模。

第一行，一个正整数 $n$。

一行，$n+1$ 个非负整数，表示对于 $s=0,1,\dots,n$ 的答案。

【样例 $1$ 说明】 当 $n=3$ 时，可以有 $2$ 或 $3$ 个格子。 若有 $2$ 个格子，则填数方案为 $[1,2]$ 或 $[2,1]$，权值共为 $2 \times C_1 \times C_2 = 4$；填色方案为 `BW`，必有一个黑色格子；$S$ 集合的选择是 $\{\},\{1\},\{2\},\{1,2\}$（以格子的编号表示）。 若有 $3$ 个格子，则填数方案为 $[1,1,1]$，权值为 $C_1^3=1$；填色方案为 `BBW`，必有两个黑色格子；$S$ 集合的选择是 $\{\},\{1\},\{2\},\{3\},\{1,3\},\{2,3\}$（以格子的编号表示）。 其中 `B` 表示黑色，`W` 表示白色。 【数据规模与约定】 **本题采用捆绑测试。** - Subtask 1（30 points）：$n\le10$。 - Subtask 2（20 points）：$n\le300$。 - Subtask 3（20 points）：$n \le 5000$。 - Subtask 4（30 points）：无特殊限制，时限为 $3.5s$。 对于 $100\%$ 的数据，$1 \le n \le 10^5$。 ### 提示 为了方便各位获得暴力分，这里给出结论： $$ C_k = \frac1k \binom{2k}{k-1} = \binom{2k-1}{k-1}-\binom{2k-1}{k-2} $$