#P9028. [2017年备战省选]tree

    ID: 9234 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-计数 DP树形 DP普通生成函数导数积分转化倍数枚举树的非对称性定理Burnside 引理模逆元

[2017年备战省选]tree

题目描述

求恰有 nn 个顶点、最大匹配恰有 mm 条边的非同构树的数量。这里的树没有根,顶点不带编号。匹配是一组两两不共享顶点的边,最大匹配是边数最多的匹配。

如果两棵树的顶点之间存在一个双射,且任意两个顶点在一棵树中相邻当且仅当它们的对应顶点在另一棵树中相邻,则称这两棵树同构。

答案对 109+710^9+7 取模。

输入格式

一行两个整数 n,mn,m,分别表示顶点数和所求最大匹配的边数。

输出格式

输出一行一个整数,表示答案。

样例 1

7 3
6

样例 2

6 2
3

数据范围

  • 对于 10%10\% 的数据,n≤5n\le 5。
  • 对于 20%20\% 的数据,n≤8n\le 8。
  • 对于 30%30\% 的数据,n≤20n\le 20。
  • 对于 50%50\% 的数据,n≤40n\le 40。
  • 有 40%40\% 的数据满足 nn 为奇数。
  • 对于全部数据,n≤70n\le 70。

原始题面见 2.pdf。