HDU 5629 Clarke and tree dp+prufer序列

题意：有中文题面 bc round 72 div1 d

分析：首先需要知道一棵无根树对应的prufer序列，如果没学过，可以看百度百科

http://baike.baidu.com/link?url=R6v5kao_NQejPfQq3A2yyAa6itaeUOrIxYwEEraSy7b2ifFJsM8CSJ6ve7BtHe2G5CakJThZ-3IMFd37zmvcQK

然后，补充一点关于prufer序列的知识

一个prufer序列唯一对应一个树，一个n个点树，对应一个长度为n-2的prufer序列

然后可以发现一个节点在prufer数列中出现的次数是这个节点的度数减一。

这样我们就知道这个数列中有哪些数了，以及这些节点出现的次数

然后问题就变成了求有多少种prufer数列，一个数列对应一个树

又因为我们知道了元素种类与出现次数。于是问题就变成了求一个有重复元素的全排列。

所以对于求节点个数为n 的树的个数，就是求排列数

然后进行dp吧

dp[i][j][k]

表示决策到第i个点，树上的点选了j个了，目前总出现次数是k的方案数

然后更新就更新看代码吧

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 55;
const LL mod = 1e9+7;
LL dp[N][N][N],c[N][N];
int a[N];
int main()
{
    c[0][0]=1;
    for(int i=1;i<=50;++i)
    {
        c[i][0]=1;
        for(int j=1;j<=50;++j)
         c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
          scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1;
        for(int i=0;i<n;++i)
        {
           for(int j=0;j<=i;++j)
           {
              for(int k=0;k<=n-2;++k)
              {
                  dp[i+1][j][k]=(dp[i+1][j][k]+dp[i][j][k])%mod;
                  for(int p=0;p<a[i+1]&&k+p<=n-2;++p)
                   dp[i+1][j+1][k+p]=(dp[i+1][j+1][k+p]+1ll*c[k+p][p]*dp[i][j][k]%mod)%mod;
              }
           }
        }
        printf("%d",n);
        for(int i=2;i<=n;++i)
        printf(" %I64d",dp[n][i][i-2]);
        printf("
");
    }
    return 0;
}