UOJ Logo Universal Online Judge

UOJ

附件下载 统计

给定整数 $n,y$ 和一个长度为 $n$ 的整数序列 $A = \{a_1,a_2,\cdots,a_n\}$,保证序列 $A$ 单调不减或单调不增

构建有向图 $G(V,E)$,其中 $V = \{1,2,\cdots,n\}$,$E = \{(i,j) \mid 1 \leq i,j \leq n, a_i \geq j\}$。注意图 $G$ 中可能包含自环。

定义边子集 $T \subseteq E$ 合法当且仅当图 $G'(V,T)$ 中每个点的入度和出度不超过 $1$,自环对对应点的入度和出度均贡献 $1$。定义一个合法边子集 $T$ 的权值为 $y^{\mathrm{cycle}(T)}$,其中 $\mathrm{cycle}(T)$ 表示图 $G'(V,T)$ 的环数,自环是一个环。

特别地,本题认为 $0^0=1$。

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

输入格式

第一行两个整数 $n,y$,第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 描述序列 $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 \leq n \leq 10^5 , 0 \leq y < 998244353 , 0 \leq a_i \leq n$。保证序列 $A$ 是单调不减或单调不增序列。

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

子任务编号$n \leq $特殊性质分值
$1$$8$$1$
$2$$15$$y=0$$9$
$3$$2000$$10$
$4$$75000$$y=1$$15$
$5$$10^5$$15$

后 $4$ 个子任务满足序列 $A$ 单调不增,设 $b_i = \sum_{j=1}^n [a_j \geq i]$,特殊性质与分值如下表所示。

子任务编号$n \leq $特殊性质分值
$6$$15$$y=0$$5$
$7$$2000$$10$
$8$$75000$对于所有满足 $a_i \geq i$ 的 $i$,$a_i \geq b_i$$15$
$9$$10^5$$20$

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

时间限制:$\texttt{3s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载