问题 1416. -- 小鸟的修路计划

1416: 小鸟的修路计划

时间限制:1000 ms 内存限制:128 MB
提交:297 解决:67
[ 提交][ 状态][ 讨论版]

题目描述

从前有m个独立的国家，它们想修一些路，使任意两个国家互相可达。于是，各国的首脑聚在一起开会，商议如何修路。此时，最富裕的国家——N国的首脑小鸟站出来说：“讨论如何修路没有意思，我们来想一下有多少种修法吧。”可是他并没有想出问题的答案，所以他想请教你，有多少种不同的修路方案能使这m个国家相互可达。
注意: 两个国家之间不应该修多条路，且不应该有一条路自己连向自己——这没有任何意义，你能明白的

输入

输入一个正整数T表示数据组数。
接下来T行，每行一组数据，输入一个正整数m，表示国家数。

输出

对于每个m输出一行，表示方案数。
注意答案可能很大，所以需要将答案对 10^9+7 取模。

样例输入

2 1 3

样例输出

1 4

提示

1<=T<=10

1<=m<=1000

来源

2019校赛online

[ 提交][ 状态][ 讨论版]
Baidu
map