QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Hackable ✓
[0]

# 6199. 数圈圈

统计

给定整数 n,y 和一个长度为 n 的整数序列 A={a1,a2,,an}保证序列 A 单调不减或单调不增

构建有向图 G(V,E),其中 V={1,2,,n}E={(i,j)1i,jn,aij}。注意图 G 中可能包含自环。

定义边子集 TE 合法当且仅当图 G(V,T) 中每个点的入度和出度不超过 1,自环对对应点的入度和出度均贡献 1。定义一个合法边子集 T权值ycycle(T),其中 cycle(T) 表示图 G(V,T) 的环数,自环是一个环。

特别地,本题认为 00=1

对于所有整数 0kn,求所有大小为 k 的合法边子集的权值和,对 998244353 取模。

输入格式

第一行两个整数 n,y,第二行 n 个整数 a1,a2,,an 描述序列 A

输出格式

一行 n+1 个整数,第 i 个整数表示大小为 i1 的合法边子集的权值和,对 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% 的数据,1n105,0y<998244353,0ain。保证序列 A 是单调不减或单调不增序列。

5 个子任务满足序列 A 单调不减,特殊性质与分值如下表所示。

子任务编号n特殊性质分值
181
215y=09
3200010
475000y=115
510515

4 个子任务满足序列 A 单调不增,设 bi=nj=1[aji],特殊性质与分值如下表所示。

子任务编号n特殊性质分值
615y=05
7200010
875000对于所有满足 aiiiaibi15
910520

请注意算法常数对运行时间带来的影响。