305025: CF954H. Path Counting
Memory Limit:256 MB
Time Limit:5 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Path Counting
题意翻译
- 有一棵根为 $1$,最大深度为 $n$ 的树,根的深度为 $1$。 - 满足树上每个深度为 $i$ 的结点有 $a_i$ 个儿子。 - 试对于每个正整数 $k\in[1,2n-2]$ 求出树上有多少条长度为 $k$ 的路径。 - $2\leq n\leq 5000$, $2\leq a_i\leq 10^9$。题目描述
You are given a rooted tree. Let's denote $ d(x) $ as depth of node $ x $ : depth of the root is $ 1 $ , depth of any other node $ x $ is $ d(y)+1 $ , where $ y $ is a parent of $ x $ . The tree has the following property: every node $ x $ with $ d(x)=i $ has exactly $ a_{i} $ children. Maximum possible depth of a node is $ n $ , and $ a_{n}=0 $ . We define $ f_{k} $ as the number of unordered pairs of vertices in the tree such that the number of edges on the simple path between them is equal to $ k $ . Calculate $ f_{k} $ modulo $ 10^{9}+7 $ for every $ 1<=k<=2n-2 $ .输入输出格式
输入格式
The first line of input contains an integer $ n $ ( $ 2<=n<=5000 $ ) — the maximum depth of a node. The second line of input contains $ n-1 $ integers $ a_{1},a_{2},...,a_{n-1} $ ( $ 2<=a_{i}<=10^{9} $ ), where $ a_{i} $ is the number of children of every node $ x $ such that $ d(x)=i $ . Since $ a_{n}=0 $ , it is not given in the input.
输出格式
Print $ 2n-2 $ numbers. The $ k $ -th of these numbers must be equal to $ f_{k} $ modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
4
2 2 2
输出样例 #1
14 19 20 20 16 16
输入样例 #2
3
2 3
输出样例 #2
8 13 6 9