给定整数 n,y 和一个长度为 n 的整数序列 A={a1,a2,⋯,an},保证序列 A 单调不减或单调不增。
构建有向图 G(V,E),其中 V={1,2,⋯,n},E={(i,j)∣1≤i,j≤n,ai≥j}。注意图 G 中可能包含自环。
定义边子集 T⊆E 合法当且仅当图 G′(V,T) 中每个点的入度和出度不超过 1,自环对对应点的入度和出度均贡献 1。定义一个合法边子集 T 的权值为 ycycle(T),其中 cycle(T) 表示图 G′(V,T) 的环数,自环是一个环。
特别地,本题认为 00=1。
对于所有整数 0≤k≤n,求所有大小为 k 的合法边子集的权值和,对 998244353 取模。
输入格式
第一行两个整数 n,y,第二行 n 个整数 a1,a2,⋯,an 描述序列 A。
输出格式
一行 n+1 个整数,第 i 个整数表示大小为 i−1 的合法边子集的权值和,对 998244353 取模。
样例一
input
2 2 2 2
output
1 6 6
explanation
图 G 中有两个点和边 {(1,1),(1,2),(2,1),(2,2)}。
大小为 0 的合法边子集仅有空集,其权值为 1,故大小为 0 的合法边子集的权值和为 1;
大小为 1 的合法边子集有 {(1,1)},{(2,2)},{(1,2)},{(2,1)},它们的权值分别为 2,2,1,1,权值和为 6;
大小为 2 的合法边子集有 {(1,1),(2,2)},{(1,2),(2,1)},它们的权值分别为 4,2,权值和为 6。
限制与约定
对于 100% 的数据,1≤n≤105,0≤y<998244353,0≤ai≤n。保证序列 A 是单调不减或单调不增序列。
前 5 个子任务满足序列 A 单调不减,特殊性质与分值如下表所示。
子任务编号 | n≤ | 特殊性质 | 分值 |
---|---|---|---|
1 | 8 | 无 | 1 |
2 | 15 | y=0 | 9 |
3 | 2000 | 无 | 10 |
4 | 75000 | y=1 | 15 |
5 | 105 | 无 | 15 |
后 4 个子任务满足序列 A 单调不增,设 bi=∑nj=1[aj≥i],特殊性质与分值如下表所示。
子任务编号 | n≤ | 特殊性质 | 分值 |
---|---|---|---|
6 | 15 | y=0 | 5 |
7 | 2000 | 无 | 10 |
8 | 75000 | 对于所有满足 ai≥i 的 i,ai≥bi | 15 |
9 | 105 | 无 | 20 |
请注意算法常数对运行时间带来的影响。