#P17894. Maximum Segment Sum

Maximum Segment Sum

题目描述

考虑所有长度为 nn、每个元素为 −1-1 或 11 的序列。

一个序列的最大子段和,是其所有连续子段的元素和的最大值。允许选择空子段,其和为 00。

对每个 k=0,1,…,nk=0,1,\ldots,n,分别计算最大子段和恰好为 kk 的序列数量。答案对 998244353998244353 取模。

输入格式

输入一行,一个整数 nn。

输出格式

输出一行 n+1n+1 个整数,依次表示 k=0,1,…,nk=0,1,\ldots,n 时的答案,对 998244353998244353 取模。

数据范围

1≤n≤5000001\le n\le500000。

样例输入

3

样例输出

1 4 2 1

样例解释

最大子段和为 00 的序列只有 (−1,−1,−1)(-1,-1,-1)。

最大子段和为 11 的四个序列为 (−1,−1,1)(-1,-1,1)、(−1,1,−1)(-1,1,-1)、(1,−1,−1)(1,-1,-1)、(1,−1,1)(1,-1,1)。

最大子段和为 22 的两个序列为 (−1,1,1)(-1,1,1)、(1,1,−1)(1,1,-1);为 33 的序列只有 (1,1,1)(1,1,1)。