HDU 5629 Clarke and tree dp+prufer序列

题目链接：

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 ;

}