Best Coder ^beta
VIP | STD Contests
DIY | Web-DIY ^beta

Clarke and tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 241 Accepted Submission(s): 111

Problem Description

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)$.

Input

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$.

Output

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$.

Sample Input

1
3
2 2 1

Sample Output

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.

Source

BestCoder Round #72 (div.1)

Statistic | Submit | Discuss | Note

Home | Top

Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-04-26 08:58:29, Gzip enabled

Administration