MEX Problem
题目描述
非负整数数组的 MEX 是没有在数组中出现的最小非负整数。例如:
$$\operatorname{MEX}([3,1,0])=2,\qquad \operatorname{MEX}([2,2,1])=0.$$
称长度为 k 的非负整数数组 b 是 k-good 数组,当且仅当 MEX(b)=k。等价地,它是 0,1,…,k−1 的一个排列。
对一个长度为 n 的 n-good 数组 p,定义 f(p) 为满足以下条件的下标对 (l,r) 的数量:
- 1≤l≤r≤n;
- 子数组 [pl,pl+1,…,pr] 是 (r−l+1)-good 数组。
可以证明 1≤f(p)≤n。给定 n,对每个 i=1,2,…,n,求满足 f(p)=i 的 n-good 数组 p 的数量,答案对 998244353 取模。
输入格式
一行一个整数 n。
输出格式
输出一行 n 个整数。第 i 个整数表示满足 f(p)=i 的数组数量对 998244353 取模的结果。
数据范围
1≤n≤105。
样例 1
1
1
样例 2
3
0 2 4
样例 3
7
0 2312 1424 728 352 160 64
n=3 时,排列 [0,2,1] 和 [1,2,0] 的函数值为 2,另外四个排列的函数值均为 3。