#P17908. Cute Young Diagram Counting

Cute Young Diagram Counting

题目描述

杨图由若干行左对齐的单位格组成,各行长度为正整数,并且从上到下不增。记其行长序列为 λ=(λ1,…,λr)\lambda=(\lambda_1,\ldots,\lambda_r)。

杨图的共轭是将所有格子的行列坐标交换得到的图形。若共轭的第 jj 行长度为 μj\mu_j,则 μj=∣{i:λi≥j}∣\mu_j=|\{i:\lambda_i\ge j\}|。

对图中的一个格子 (i,j)(i,j),定义锚定于它的子图为所有满足 x≥i,y≥jx\ge i,y\ge j 的格子 (x,y)(x,y)。一次操作可以将这部分子图共轭,再放回同一锚点;其余格子不变。坐标变换为

(x,y)⟼(i+y−j, j+x−i).(x,y)\longmapsto(i+y-j,\ j+x-i).

只有变换后整个格子集合仍是合法杨图时,操作才允许执行。

定义一个杨图的可爱度为:从它出发,执行任意次(包括零次)合法操作,可以得到的不同杨图的数量。

给定不增的正整数序列 a1,…,ana_1,\ldots,a_n,对于每个 i=1,…,ni=1,\ldots,n,求行长为 (a1,…,ai)(a_1,\ldots,a_i) 的杨图的可爱度,答案对 998244353998244353 取模。

输入格式

第一行为 nn,第二行为 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

输出 nn 个以空格分隔的整数,依次为每个前缀的答案。

数据范围

1≤n≤10000001\le n\le1000000,n≥a1≥a2≥⋯≥an≥1n\ge a_1\ge a_2\ge\cdots\ge a_n\ge1。本题只有一组数据。

样例输入

3
3 2 1

样例输出

2 3 1

样例说明

(3)(3) 可变为 (3)(3)、(1,1,1)(1,1,1);(3,2)(3,2) 可变为 (3,2)(3,2)、(3,1,1)(3,1,1)、(2,2,1)(2,2,1);(3,2,1)(3,2,1) 只能得到自身。