【XSY2519】神经元 prufer序列 DP

题目描述

　　有\(n\)点，每个点有度数限制，\(\forall i(1\leq i\leq n)\)，让你选出\(i\)个点，再构造一棵生成树，要求每个点的度数不超过度数限制。问你有多少种方案。

　　\(n\leq 100\)

题解

　　考虑prufer序列。

　　每个prufer序列唯一对应一棵无根树。

　　设\(f_{i,j,k}\)为前\(i\)个点选了\(j\)个点，目前的prufer序列长度为\(k\)的方案数。

　　每次枚举下一个点选不选和度数

　　不选：\(f_{i+1,j,k}+=f_{i,j,k}\)

　　选，度数为\(l\)：\(f_{i+1,j+1,k+l-1}+=f_{i,j,k}\times\binom{k+l-1}{k}\)

　　答案为\(f_{n,i,i-2}\)

　　时间复杂度：\(O(n^4)\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

ll p=1000000007;

ll c[110][110];

ll f[110][110][110];

int d[110];

void add(ll &a,ll b)

{

	a=(a+b)%p;

}

int main()

{

	int n;

	scanf("%d",&n);

	int i,j,k,l;

	for(i=1;i<=n;i++)

		scanf("%d",&d[i]);

	for(i=0;i<=n;i++)

	{

		c[i][0]=1;

		for(j=1;j<=i;j++)

			c[i][j]=(c[i-1][j]+c[i-1][j-1])%p;

	}

	f[0][0][0]=1;

	for(i=0;i<n;i++)

		for(j=0;j<=i;j++)

			for(k=0;k<=n-2;k++)

				if(f[i][j][k])

				{

					add(f[i+1][j][k],f[i][j][k]);

					for(l=0;l<=d[i+1]-1&&k+l<=n-2;l++)

						add(f[i+1][j+1][k+l],f[i][j][k]*c[k+l][k]);

				}

	printf("%d\n",n);

	for(i=2;i<=n;i++)

		printf("%lld\n",f[n][i][i-2]);

	return 0;

}