#1913. A+B Problem
A+B Problem
A+B Problem
题目描述
标题: A+B Problem - Problem - QOJ.ac
#10348. A+B Problem
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