题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=562
题意：
求给每个节点的度数允许的最大值，让你求k个节点能组成的不同的生成树个数。
题解：
对于n个节点形成的一颗生成树，有一个与之唯一对应的大小为n-2的prufer数列。
并且一个节点的度数减一为它出现在prufer数列中的次数。
那么我们求生成树的个数可以转化为求prufer数列的可重集排列，而这个可以用dp来做。
dp[i][j][k]表示处理到第i个节点，已经用了j个节点，且可重集大小为k的排列组合数。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std; const int maxn = ;
const int mod = 1e9 + ;
typedef long long LL; int n;
LL dp[maxn][maxn][maxn];
int arr[maxn]; LL C[maxn][maxn];
void pre() {
C[][] = ;
for (int i = ; i < maxn; i++) {
C[i][] = ;
for (int j = ; j <= i; j++) {
C[i][j] = (C[i - ][j - ] + C[i - ][j]) % mod;
}
}
} void init() {
memset(dp, , sizeof(dp));
} int main() {
pre();
int tc;
scanf("%d", &tc);
while (tc--) {
init();
scanf("%d", &n);
for (int i = ; i <= n; i++) {
scanf("%d", &arr[i]);
}
dp[][][] = ;
for (int i = ; i <= n; i++) {
for (int j = ; j <= i; j++) {
for (int k = ; k <= n - ; k++) {
//不用第i+1个数
dp[i + ][j][k] = (dp[i + ][j][k] + dp[i][j][k]) % mod;
//用第i+1个数
for (int l = ; l <= arr[i + ] && l - + k <= n - ; l++) {
dp[i + ][j + ][k + l - ] = (dp[i + ][j + ][k + l - ] + C[k + l - ][l - ] * dp[i][j][k]) % mod;
}
}
}
}
printf("%d", n);
for (int i = ; i <= n; i++) printf(" %lld", dp[n][i][i - ]);
printf("\n");
}
return ;
}