#P6509. Tree

    ID: 5113 传统题 2000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-图论独立集二分图匹配动态规划树形 DP多项式与生成函数普通生成函数生成函数求系数Lagrange 反演组合数学Pascal 递推模拟与实现技巧高精度加法高精度乘法高精度除法CF2700

Tree

题目描述

给出一个数 nn,对每个 x∈[1,n],y∈[0,n]x\in[1,n],y\in[0,n],求有多少棵树有 xx 个节点且最大点独立集为 yy。

注意,树无标号,但儿子有顺序,以下不是同一棵树:

WsUBpd.png

WsUIcn.png

输入格式

一行一个数 nn。

输出格式

nn 行,每行 n+1n+1 个数,第 ii 行第 jj 个数表示 x=i,y=j−1x=i,y=j-1 时的答案。

样例

15
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 3 2 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 12 2 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 15 25 2 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 88 42 2 0 0 0 0 0 0 0 0 0 
0 0 0 0 91 273 63 2 0 0 0 0 0 0 0 0 
0 0 0 0 0 700 640 88 2 0 0 0 0 0 0 0 
0 0 0 0 0 612 2856 1275 117 2 0 0 0 0 0 0 
0 0 0 0 0 0 5814 8550 2280 150 2 0 0 0 0 0 
0 0 0 0 0 0 4389 29260 21175 3773 187 2 0 0 0 0 
0 0 0 0 0 0 0 49588 106260 46046 5888 228 2 0 0 0 
0 0 0 0 0 0 0 32890 296010 313950 91000 8775 273 2 0 0 
0 0 0 0 0 0 0 0 430560 1261260 802620 167076 12600 322 2 0 

数据范围

  • 对 30%30\% 的数据,n≤50n\le 50。

  • 对 60%60\% 的数据,n≤200n\le 200。

  • 对 100%100\% 的数据,n≤500n\le 500。