#1913. A+B Problem

    ID: 1913 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 入门 上传者: 标签>CTT赛事:contest1970来源:qoj.ac数据:公开样例强连通分量数学

A+B Problem

A+B Problem

题目描述

标题: A+B Problem - Problem - QOJ.ac

#10348. A+B Problem

Statistics

The problem was used in the following contests:

题目名字是吸引你点进来的~~~

JOHNKRAM最近在研究图论。今天他遇到了这样一道题:给一张有向图,保证没有重边和自环。求把这张图的强连通分量缩成点之后,有多少个点入度为0。

JOHNKRAM使用 tarjan 算法轻而易举地切掉了这道题。但他发现有很多人代码写得比他短多了,于是他要来了程序,结果发现这个程序是打印1的= =。难道随机数据真的这么水吗?于是他随机生成了很多张有向图,结果他发现答案真的全是1= =。于是他更改了随机生成的方式,只生成每个强连通分量大小都属于某个集合S的有向图,结果答案立刻就变大了。

现在JOHNKRAM把那些人都卡掉了,但他想证明一下数据的强度,所以他提出了一个问题:对于所有带标号点数为i(1≤i≤n)的每个强连通分量大小都属于集合S的有向图,之前问题的答案的期望是多少?他发现自己不会证明了,于是他来向你请教。

输入格式

输入第一行包含1个正整数n,表示生成的有向图的最大点数。

接下来n行,第i行包含一个整数si。如果si=1,则i在集合S中,否则i不在集合S中。

输出格式

共输出n行,每行包含一个整数。第i行的整数表示对于所有带标号点数为i(1≤i≤n)的每个强连通分量大小都属于集合S的有向图,之前问题的答案的期望mod 998244353的结果,如果没有合法的有向图则输出0。设期望值为a/b(a和b为互质的正整数),你输出的整数为x,则你需要保证bx≡a(mod 998244353)且0≤x<998244353。

样例数据

样例输入

3
1
0
0

样例输出

1
332748119
519087065

样例说明

点数为1的有向图中,答案为1的合法有向图有1张,所以答案为1,mod 998244353后为1。

点数为2的有向图中,答案为1的合法有向图有2张,答案为2的合法有向图有1张,所以答案为43,mod 998244353后为332748119。

点数为3的有向图中,答案为1的合法有向图有15张,答案为2的合法有向图有9张,答案为3的合法有向图有1张,所以答案为3625,mod 998244353后为519087065。

数据规模和约定

对于全部测试数据,1≤n≤100000,0≤si≤1。

测试点编号 n≤ 其他约定 1 4 无 2 1000 ∀1≤i≤⌈n2⌉,si=0 3 1000 ∀1≤i≤n,si=[i1] 4 1000 ∀1≤i≤n,si=[i1] 5 1000 ∀1≤i≤n,si=[i1] 6 1000 ∀1≤i≤⌈n3⌉,si=0 7 1000 ∀1≤i≤⌈n3⌉,si=0 8 1000 ∀1≤i≤⌈n3⌉,si=0 9 1000 ∃x,∀1≤i≤n,si=[ix] 10 1000 ∃x,∀1≤i≤n,si=[ix] 11 1000 ∃x,∀1≤i≤n,si=[ix] 12 1000 无 13 1000 无 14 1000 无 15 100000 无 16 100000 无 17 100000 无 18 100000 无 19 100000 无 20 100000 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
1
0
0
1
332748119
519087065