P7512 "Byakkai OI 2021" Eaquira

Given $n$, take the integer points on the number line in $[1,n]$. Define a **maximal consecutive black segment** as an interval $[L,R]$ with $1 \le L \le R \le p$, such that all intervals with indices in $[L,R]$ are black, and it cannot be extended further; that is, the intervals with indices $L-1$ (if it exists; same below) and $R+1$ are both white. First, you need to partition them into several intervals $[l_1,r_1],[l_2,r_2],\dots,[l_p,r_p]$, satisfying $l_1 = 1$, $r_p = n$, and for $1 \le i < p$ we have $r_i = l_{i+1}-1$; for $1 \le i \le p$ we have $l_i \le r_i$. Second, you need to mark each interval as black or white, but it is not allowed that both the first interval and the $p$-th interval are marked black at the same time. Third, within each interval, select a subinterval, called a **wonderful subinterval**. Fourth, in each maximal consecutive black segment, select one black interval, called a **wonderful black interval**. Fifth, among all maximal consecutive black segments, designate some of them as **wonderful maximal consecutive black segments**. Define the weight of a plan determined by the above steps as the sum of the number of black intervals and the number of wonderful maximal consecutive black segments. Originally, I hoped you would compute, for $s = 0,1,2,\dots,n$, the number of plans that make the final weight equal to $s$. However, I have also prepared some easier challenges. See the input format for details. The answer should be taken modulo $998244353$.

One line with two integers $n,{\rm type}$. If ${\rm type} = 0$, you need to compute, for $0 \le s \le n$, the number of plans with weight $s$. If ${\rm type} = 1$, you need to compute the total number of plans over all $0 \le s \le n$.

If ${\rm type} = 0$, output one line with $n+1$ non-negative integers, in order, representing the answers for $s = 0,1,2,\dots,n$. If ${\rm type} = 1$, output one line with one non-negative integer, representing the answer.

**Sample Explanation** Below, $0$ denotes black and $1$ denotes white. For the first sample, consider the $4$ partitions of $[1,3]$: - $[1,1],[2,2],[3,3]$: At this time, the number of ways to choose an unordered pair is $1$. Considering the black/white marking of each interval, there are the following $4$ plans: - $001,100$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $2$ or $3$. The number of ways to choose the wonderful black interval is $2$. - $101$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $1$ or $2$. The number of ways to choose the wonderful black interval is $1$. - $[1,2],[3,3]$ or $[1,1],[2,3]$: At this time, the number of ways to choose an unordered pair is $3$. Considering the black/white marking of each interval, there are the following $2$ plans: - $01,10$: in this case, you may choose whether to mark the only maximal consecutive black segment as wonderful or not, so the weight is $1$ or $2$. The number of ways to choose the wonderful black interval is $1$. - $[1,3]$: At this time, the number of ways to choose an unordered pair is $6$. Considering the black/white marking of each interval, there is the following $1$ plan: - $1$: in this case, the weight is $0$, the total number of plans is $6$, and the number of ways to choose the wonderful black interval is $1$. Therefore, the number of plans with weight $0$ is $6 \times 1 = 6$, the number of plans with weight $1$ is $1 \times 1 + 2 \times 3 \times 2 \times 1 = 13$, the number of plans with weight $2$ is $1 \times 2 \times 2 + 1 \times 1 + 2 \times 3 \times 2 \times 1 = 17$, and the number of plans with weight $3$ is $1 \times 2 \times 2 = 4$. For the second sample, no explanation is provided. **Constraints** **This problem uses bundled testdata.** The specific subtask constraints and scores are as follows: |Subtask ID|Score|$n \le $|${\rm type} =$|Time limit / 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$| For all testdata, $1 \le n \le 2 \times 10^5$, ${\rm type} \in \{0,1\}$. Translated by ChatGPT 5