CF1806D.DSU Master
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an integer n and an array a of length n−1 whose elements are either 0 or 1 .
Let us define the value of a permutation † p of length m−1 ( m≤n ) by the following process.
Let G be a graph of m vertices labeled from 1 to m that does not contain any edges. For each i from 1 to m−1 , perform the following operations:
- define u and v as the (unique) vertices in the weakly connected components ‡ containing vertices pi and pi+1 respectively with only incoming edges †† ;
- in graph G , add a directed edge from vertex v to u if api=0 , otherwise add a directed edge from vertex u to v (if api=1 ).
Note that after each step, it can be proven that each weakly connected component of G has a unique vertex with only incoming edges.Then, the value of p is the number of incoming edges of vertex 1 of G .
For each k from 1 to n−1 , find the sum of values of all k! permutations of length k . Since this value can be big, you are only required to compute this value under modulo 998244353 .
Operations when n=3 , a=[0,1] and p=[1,2] † A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array), and [1,3,4] is also not a permutation ( n=3 but there is 4 in the array).
‡ The weakly connected components of a directed graph is the same as the components of the undirected version of the graph. Formally, for directed graph G , define a graph H where for all edges a→b in G , you add an undirected edge a↔b in H . Then the weakly connected components of G are the components of H .
†† Note that a vertex that has no edges is considered to have only incoming edges.
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n ( 2≤n≤5⋅105 ).
The second line of each test case contains n−1 integers a1,a2,…,an−1 ( ai is 0 or 1 ).
It is guaranteed that the sum of n over all test cases does not exceed 5⋅105 .
输出格式
For each test case, output n−1 integers in a line, the i -th integer should represent the answer when k=i , under modulo 998244353 .
输入输出样例
输入#1
2 3 0 0 9 0 1 0 0 0 1 0 0
输出#1
1 3 1 2 7 31 167 1002 7314 60612
说明/提示
Consider the first test case.
When k=1 , there is only 1 permutation p .
- When p=[1] , we will add a single edge from vertex 2 to 1 . Vertex 1 will have 1 incoming edge. So the value of [1] is 1 .
Therefore when k=1 , the answer is 1 .
When k=2 , there are 2 permutations p .
- When p=[1,2] , we will add an edge from vertex 2 to 1 and an edge from 3 to 1 . Vertex 1 will have 2 incoming edges. So the value of [1,2] is 2 .
- When p=[2,1] , we will add an edge from vertex 3 to 2 and an edge from 2 to 1 . Vertex 1 will have 1 incoming edge. So the value of [2,1] is 1 .
Therefore when k=2 , the answer is 2+1=3 .