#2048. 数圈圈

    ID: 2048 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest767来源:qoj.ac数据:公开样例枚举前缀和

数圈圈

数圈圈

题目描述

标题: 数圈圈 - Problem - QOJ.ac

#6199. 数圈圈

Statistics

The problem was used in the following contests:

给定整数 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≤特殊性质分值 18无1 215y=09 32000无10 475000y=115 5105无15

后 4 个子任务满足序列 A 单调不增,设 bi=∑j=1n[aj≥i],特殊性质与分值如下表所示。

子任务编号n≤特殊性质分值 615y=05 72000无10 875000对于所有满足 ai≥i 的 i,ai≥bi15 9105无20

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 2
2 2
1 6 6