#P17928. MEX Problem

MEX Problem

MEX Problem

题目描述

非负整数数组的 MEX⁡\operatorname{MEX} 是没有在数组中出现的最小非负整数。例如:

$$\operatorname{MEX}([3,1,0])=2,\qquad \operatorname{MEX}([2,2,1])=0.$$

称长度为 kk 的非负整数数组 bb 是 kk-good 数组,当且仅当 MEX⁡(b)=k\operatorname{MEX}(b)=k。等价地,它是 0,1,…,k−10,1,\ldots,k-1 的一个排列。

对一个长度为 nn 的 nn-good 数组 pp,定义 f(p)f(p) 为满足以下条件的下标对 (l,r)(l,r) 的数量:

  • 1≤l≤r≤n1\le l\le r\le n;
  • 子数组 [pl,pl+1,…,pr][p_l,p_{l+1},\ldots,p_r] 是 (r−l+1)(r-l+1)-good 数组。

可以证明 1≤f(p)≤n1\le f(p)\le n。给定 nn,对每个 i=1,2,…,ni=1,2,\ldots,n,求满足 f(p)=if(p)=i 的 nn-good 数组 pp 的数量,答案对 998244353998244353 取模。

输入格式

一行一个整数 nn。

输出格式

输出一行 nn 个整数。第 ii 个整数表示满足 f(p)=if(p)=i 的数组数量对 998244353998244353 取模的结果。

数据范围

1≤n≤1051\le n\le10^5。

样例 1

1
1

样例 2

3
0 2 4

样例 3

7
0 2312 1424 728 352 160 64

n=3n=3 时,排列 [0,2,1][0,2,1] 和 [1,2,0][1,2,0] 的函数值为 22,另外四个排列的函数值均为 33。