Codeforces 724F. Uniformly Branched Trees(无根树计数DP)

Author Avatar
Sakits 5月 09, 2018

题解

  第一次写无根树计数,记录一下…
  令fi,j,kf_{i,j,k}表示ii个点,根有jj个子树,最大的子树大小不超过kk的方案数,转移如下:

fi,j,k=fi,j,k1+l=1jfikl,jl,k1×(fk,d1,k1+l1l)f_{i,j,k}=f_{i,j,k-1}+\sum_{l=1}^{j}f_{i-k*l,j-l,k-1}\times \binom{f_{k,d-1,k-1}+l-1}{l}

  后面的组合数是nn种物品可重复地选mm个的方案数,用隔板法。
  然后考虑无根树怎么办,上方的DP是确定一个根的,如果直接随便找一个点当根来计数显然会多计算方案,因为可能有很多个点的子树大小是我们给定的大小。
  但是我们考虑到一个树只有121\sim 2个重心,并且只有重心的子树大小最多是n2\frac{n}{2},所以我们可以找重心当作根DP。
  如果点数为奇数,那么显然只有一个重心,fn,d,n2f_{n,d,\frac{n}{2}}就是答案。
  如果点数为偶数,那么我们还要减去有两个重心的树的个数,显然有两个重心时,把重心之间相连的边断掉会得到两个大小为n2\frac{n}{2}的树,所以在大小为n2\frac{n}{2}的树中选两个拼起来就是多算的两个重心的方案数了,方案数为(fn2,d1,n212)\binom{f_{\frac{n}{2},d-1,\frac{n}{2}-1}}{2}

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=2010;
int n, m, mod;
int inv[maxn], f[maxn][12][maxn>>1];

inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline int power(int a, int b)
{
	int ans=1;
	for(;b;b>>=1, a=1ll*a*a%mod)
	if(b&1) ans=1ll*ans*a%mod;
	return ans;
}

int main()
{
	read(n); read(m); read(mod);
	if(n<=2) return puts("1"), 0;
	for(int i=1;i<=n;i++) inv[i]=power(i, mod-2);
	for(int i=0;i<=n/2;i++) f[1][0][i]=1;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=1;k<=n/2;k++)
			{
				f[i][j][k]=f[i][j][k-1];
				for(int l=1, tmp=1;l<=j && k*l<=i;l++)
				{
					tmp=1ll*tmp*(f[k][(k==1)?0:m-1][k-1]+l-1)%mod*inv[l]%mod;
					f[i][j][k]=(f[i][j][k]+1ll*f[i-k*l][j-l][k-1]*tmp)%mod;
				}
			}
		}
	}
	int ans=f[n][m][n>>1];
	if((n&1)==0)
	{
		int t=f[n>>1][m-1][(n>>1)-1];
		printf("%d %lld\n", t, 1ll*t*(t-1)/2);
		ans=(ans-1ll*t*(t-1)/2%mod+mod)%mod;
	} 
	printf("%d\n", ans);
}