题面
有n个点，它们从1到n进行标号，第i个点的限制为度数不能超过A[i].
现在对于每个s (1 <= s <= n)，问从这n个点中选出一些点组成大小为s的有标号无根树的方案数。
100%的数据：n <= 100
100
prufer序列
每个大小为n，有标号无根树都可以表示成一个长度为(n-2)且取值在[1,n]的序列。
这个序列就叫prufer序列。
树转prufer序列
1.每次查找一个标号最小且度数为一的点，使与之相连的点的编号加入序列尾；
2.删除树中的这个点。
prufer序列转树
1.新建一个包含[1,n]的集合；
2.找出集合中在序列中未出现的最小编号，并使之与序列头连一条边；
3.删除集合中的这个编号，以及序列头；
4.重复2-3步骤n-2次，序列则为空；
5.把集合中的剩余两个编号相连，原树复原。
性质
1.长度为(n-2)的prufer序列的集合与大小为n的带标号无根树的集合一一映射。
2.带标号无根树的任意点的度数等于，与之对应的prufer序列的对应编号出现次数+1。
Back to Problem
Pre
假设我们求出了一个prufer序列的长度(n)，并且知道其中每个编号出现的次数(c_i)。
由性质2，那么这种prufer序列的贡献就是，它的不同全排列数，有：
[Ans=n!*sum_{i=1}^nfrac{1}{c_i!}
]
正文
所以我们把原题转化为在序列上的动态规划。
设(f_{i,j,k})表示前i个点，用了j个点，序列长度为k的方案数。
那么就有，
[f_{i,j,k} Rightarrow egin{cases}
f_{i+1,j,k}\
f_{i+1,j+1,k+l},&l in [0,a_i-1]
end{cases}
]
最终答案就是(f_{n,s,s-2}*(s-2)!)。
时间复杂度为(O(n^4))，但由于冗余状态的存在，是能卡过的。
原题是要用FFT优化到(O(n^3*log_n))
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const char* fin="tree.in";
const char* fout="tree.out";
const int inf=0x7fffffff;
const int maxn=107,mo=1004535809;
int n,a[maxn],f[maxn][maxn][maxn],fact[maxn],nf[maxn];
int qpower(int a,int b){
int c=1;
while (b){
if (b&1) c=1LL*a*c%mo;
a=1LL*a*a%mo;
b>>=1;
}
return c;
}
int ni(int v){return qpower(v,mo-2);}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d",&n);
fact[0]=1;
fo(i,1,maxn-1) fact[i]=1LL*fact[i-1]*i%mo;
fo(i,0,maxn-1) nf[i]=ni(fact[i]);
fo(i,1,n) scanf("%d",&a[i]);
memset(f,0,sizeof f);
f[1][0][0]=1;
fo(i,1,n)
fo(j,0,i-1)
fo(k,0,n){
f[i+1][j][k]=(f[i][j][k]+f[i+1][j][k])%mo;
fo(l,0,a[i]-1){
if (k+l>n) break;
f[i+1][j+1][k+l]=(f[i+1][j+1][k+l]+1LL*f[i][j][k]*nf[l])%mo;
}
}
printf("%d ",n);
fo(i,2,n) cout<<1LL*f[n+1][i][i-2]*fact[i-2]%mo<<" ";
return 0;
}