5629：Clarke and tree

题目描述

Clarke is a patient with multiple personality disorder. One day, Clarke turned into a CS, did a research on data structure.
Now Clarke has $n$ nodes, he knows the degree of each node no more than $a_i$. He wants to know the number of ways to choose some nodes to compose to a tree of size $s(1 \le s \le n)$.

输入解释

The first line contains one integer $T(1 \le T \le 10)$, the number of test cases.
For each test case:
The first line contains an integer $n(2 \le n \le 50)$.
Then a new line follow with $n$ numbers. The $i$th number $a_i(1 \le a_i < n)$ denotes the number that the degree of the $i$th node must no more than $a_i$.

输出解释

For each test case, print a line with $n$ integers. The $i$th number denotes the number of trees of size $i$ modulo $10^9+7$.

输入样例

1
3
2 2 1

输出样例

3 3 2

Hint:
At first we know the degree of node 1 can not more than 2, node 2 can not more than 2, node 3 can not more than 1. So  
For the trees of size 1, we have tree ways to compose, are 1, 2 and 3. i.e. a tree with one node.  
For the trees of size 2, we have tree ways to compose, are 1-2, 1-3, 2-3.  
For the trees of size 3, we have two ways to compose, are 1-2-3, 2-1-3.

来自杭电HDUOJ的附加信息

Recommend

hujie

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 BestCoder Round #72 (div.1)

源链接： HDU-5629

最后修改于 2020-10-25T23:24:20+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	65536/65536K(Java/Others)