题目描述
考虑所有长度为 n、每个元素为 −1 或 1 的序列。
一个序列的最大子段和,是其所有连续子段的元素和的最大值。允许选择空子段,其和为 0。
对每个 k=0,1,…,n,分别计算最大子段和恰好为 k 的序列数量。答案对 998244353 取模。
输入格式
输入一行,一个整数 n。
输出格式
输出一行 n+1 个整数,依次表示 k=0,1,…,n 时的答案,对 998244353 取模。
数据范围
1≤n≤500000。
样例输入
3
样例输出
1 4 2 1
样例解释
最大子段和为 0 的序列只有 (−1,−1,−1)。
最大子段和为 1 的四个序列为 (−1,−1,1)、(−1,1,−1)、(1,−1,−1)、(1,−1,1)。
最大子段和为 2 的两个序列为 (−1,1,1)、(1,1,−1);为 3 的序列只有 (1,1,1)。