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
说明
This the tree from the first sample:
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF954H/8a09c9c56935b94e970d5753d7484c0e7a756d44.png)