#P5346. 树

    ID: 4359 传统题 1000ms 256MiB 尝试: 46 已通过: 23 难度: 7 上传者: 标签>CF2200提高Prüfer 序列计数 DP阶乘逆元预处理滚动数组快速幂

树

题目描述

有 nn 个编号为 1,…,n1,\ldots,n 的顶点,第 ii 个顶点的度数上限为 AiA_i。对于每个 s=1,…,ns=1,\ldots,n,求从这些顶点中选出 ss 个,并在所选顶点上组成一棵满足各点度数上限的有标号无根树的方案数。

顶点集合不同或边集合不同的方案分别计数。单个顶点组成的树没有边,其度数为 00。

输入格式

第一行一个整数 nn。第二行 nn 个整数 A1,…,AnA_1,\ldots,A_n。

输出格式

输出一行 nn 个整数,第 ss 个整数为选取 ss 个顶点时的方案数对 10045358091004535809 取模后的结果。

样例

3
2 2 1
3 3 2

数据范围

  • 20%20\% 的数据满足 n≤6n\le6。
  • 60%60\% 的数据满足 n≤50n\le50。
  • 所有数据满足 1≤n≤1001\le n\le100。

原 PDF 题面