2016-07-12

『湖南省队集训』疯狂BB的zy

题目

题目描述

zy 超强，总是想些奇怪的问题。

一天，他脑洞出了这样一个问题。有$n$个点，每个点的度数不超过$A_i$, 问从中选出一些点形成一颗大小为$s(1 \leq s \leq n)$的树的方案数。 zy 自然$O(n)$秒掉了这题，于是他想用这个问题考考你，来显示自己的强大。

输入描述

第一行有一个整数$n$。

第二行$n$个数表示$A_i$。

输出描述

一行$n$个数，第$s$个数表示形成大小为$s$的树的方案数对$1004535809(497 \times 2^{21} + 1)$取模的结果。

样例输入

3
2 2 1

样例输出

3 3 2

数据范围

对于$20\%$的数据，$n \leq 6$；

对于$60\%$的数据，$n \leq 50$；

对于$100\%$的数据，$n \leq 100$。

题解

考虑无根树的prufer序列。一个结点在prufer序列中出现的次数就等于它的度数$-1$，因此问题就转化为在序列中每个数出现次数有限制的计数问题。

考虑如下的状态表示：$ans[i][j][k]$表示计算到前$i$个结点时，已经考虑过$j$个结点，并且已经填上序列中的$k$个位置的方案数。

那么转移就很显然了，首先不考虑就是$ans[i][j][k] = ans[i - 1][j][k]$，考虑的话，还需要枚举该结点编号出现次数$time(0 \leq time < A[i])$，这样带来的方案总数为

$$\sum_{time = 0}^{k}C_{k}^{time}ans[i - 1][j - 1][k - time]$$

两种情况相加即可。这个DP的时间复杂度显然是$O(n^4)$。

最后的输出嘛，首先输出$1$个结点的答案$n$，然后对每个$s$输出$ans[n][s][s - 2]$，其中$s - 2$就是prufer序列的长度。

代码

#include <cstdio>
#define MAXN 120
#define MOD 1004535809
int C[MAXN][MAXN];
int ans[MAXN][MAXN][MAXN];
int n;
int a[MAXN];
int main()
{
	freopen("zy.in", "r", stdin);
	freopen("zy.out", "w", stdout);
	scanf("%d", &n);
	C[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; j++)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
	}
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	ans[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++)
				ans[i][j][k] = (ans[i][j][k] + ans[i - 1][j][k]) % MOD;
		for (int time = 0; time < a[i]; time++)
			for (int j = 1; j <= i; j++)
				for (int k = time; k <= n; k++)
					ans[i][j][k] = (ans[i][j][k] + (long long)C[k][time] * ans[i - 1][j - 1][k - time] % MOD) % MOD;
	}
	printf("%d", n);
	for (int i = 2; i <= n; i++)
		printf(" %d", ans[n][i][i - 2]);
	printf("\n");
	return 0;
}