#P5346. 树
树
题目描述
有 个编号为 的顶点,第 个顶点的度数上限为 。对于每个 ,求从这些顶点中选出 个,并在所选顶点上组成一棵满足各点度数上限的有标号无根树的方案数。
顶点集合不同或边集合不同的方案分别计数。单个顶点组成的树没有边,其度数为 。
输入格式
第一行一个整数 。第二行 个整数 。
输出格式
输出一行 个整数,第 个整数为选取 个顶点时的方案数对 取模后的结果。
样例
3
2 2 1
3 3 2
数据范围
- 的数据满足 。
- 的数据满足 。
- 所有数据满足 。
有 n 个编号为 1,…,n 的顶点,第 i 个顶点的度数上限为 Ai。对于每个 s=1,…,n,求从这些顶点中选出 s 个,并在所选顶点上组成一棵满足各点度数上限的有标号无根树的方案数。
顶点集合不同或边集合不同的方案分别计数。单个顶点组成的树没有边,其度数为 0。
第一行一个整数 n。第二行 n 个整数 A1,…,An。
输出一行 n 个整数,第 s 个整数为选取 s 个顶点时的方案数对 1004535809 取模后的结果。
3
2 2 1
3 3 2