树

Time Limit: 10 Sec Memory Limit: 256 MB

Description

有n个点，它们从1到n进行标号，第i个点的限制为度数不能超过Ai
现在对于每个s(1≤s≤n)，问从这n个点中选出一些点组成大小为s 的有标号无根树的方案数。

Input

第一行一个整数n，

第二行n个整数表示Ai

Output

输出一行n个整数，第i个整数表示s=i时的答案

Sample Input

3
　　2 2 1

Sample Output

3 3 2

HINT

img

Solution

由于是带标号的无根树的计数，于是我们运用prufer编码的性质来解题。

prufer编码的几个性质：
　　　　1.对于大小为s的树，prufer编码是一个长度为 s-2 的序列；
　　　　2.i在序列中出现的次数<deg[i]；
　　　　3.一个prufer编码表示一棵树。

所以这题可以转化为求prufer编码的计数。

我们令f[i][j][k]表示前i个点，选择了j个，prufer编码长度为k的方案数。那么显然有

img

其中 f[i-1][j][k] 表示不选择该点的方案数，后面的式子表示选择了该点的方案数，选择该点可以在编码中出现0-deg[i]-1次，然后在编码中的出现顺序可以任意所以要乘上C。

最后如果i=1显然输出n，否则由于prufer编码是长度i-2的序列，所以输出f[n][i][i-2]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;
const int ONE=105;
const int MOD=1004535809;

int n;
int deg[ONE];
int C[ONE][ONE];
int f[ONE][ONE][ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

void Mod(int &a)
{
    if(a>MOD) a-=MOD;
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++) deg[i]=get();

    C[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=n;j++)
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
    }

    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++)
            for(int k=0;k<=n;k++)
            {
                f[i][j][k] += f[i-1][j][k]; Mod(f[i][j][k]);
                if(!j) continue;
                for(int l=0; l < deg[i] && l <= k ;l++)
                {
                    f[i][j][k] += (s64)f[i-1][j-1][k-l] * C[k][l] % MOD;
                    Mod(f[i][j][k]);
                }
            }

    for(int i=1;i<=n;i++)
    {
        if(i==1) printf("%d ",n);
        else printf("%d ",f[n][i][i-2]);
    }
}