勘探[jzoj6494]

发表于 分类于

题意

problem

题解

$L$ 为奇数

首先来看看 $50$ 分的。

这时候重心在边上，这条边将树分成了两部分，且这两部分中叶子结点到根的路径为长度为 $\frac{L-1}{2}$。

那么设 $f_{i,j}$ 表示 $i$ 个点，最长路径的长度为 $j$ 的有根树的方案数。

考虑从 $f_{k,j-1}$ 转移过来，因为根节点已经是固定了的，所以儿子中只要有一个 $f_{k,j-1}$ 即可满足条件。

显然我们不能一个个枚举儿子选什么，因为会出现重复的情况，为避免之，再枚举儿子中最长路径长度为 $j-1$ 的节点个数，假设有 $l$ 个。

那么后面这个系数相当于是在 $f_{k,j-1}$ 棵树中选出 $l$ 个形成一个集合，可以重复选的方案数。由插板法可知，系数为 $\binom{f_{k,j-1}+l-1}{l}$。

那么则有：$f_{i,j}=\sum_{k}\sum_{l}f_{i-kl,j}\binom{f_{k,j-1}+l-1}{l}$。

需要注意一下枚举的顺序，且 $l$ 从小到大枚举即可用 $l-1$ 的组合数来 $O(1)$ 算出 $l$ 时的组合数。

但这只是最长路径长度为 $j-1$ 的，还可以有其他长度小于 $j-1$ 的可以插进去。

那么再维护多一个 $g_{i,j}$ 表示 $i+1$ 个点（除去根节点外还有 $i$ 个），最长路径的长度 $\leq j$ 的有根树的方案数。

用现在的 $f_j$ 和 $g_{j-1}$ 卷积以后就得到了真正的 $f_{i,j}$ 了。

然后再维护 $g$ 数组，方法和 $f$ 的是几乎一样的。

算出了 $f$ 数组，接下来的就很容易了。

枚举两部分中节点个数较少的节点个数 $i$，然后将 $f_{i,\frac{L-1}{2}}\times f_{n-i,\frac{L-1}{2}}$ 相加就是答案了。

需要注意一下当 $i=\frac{n}{2}$ 时的方案数。

$L$ 为偶数

然后再来考虑 $L$ 为偶数的。设 $x=\frac{L}{2}$。

和奇数类似，现在重心是一个点，将树分成了若干部分。但是可能会有很多棵子树。

我们需要满足至少有两棵子树的高度恰好为 $x-1$，且所有的子树高度都不能超过 $x-1$。

考虑容斥，用 $f_{n,x}$ 减去只有一棵子树的高度为 $x-1$ 的方案数。

那么枚举这个子树的节点个数 $i$，则此时方案数为 $f_{i,x-1}\times g_{n-i,x-1}$。

这个节点个数 $i$ 满足 $i\geq x,n-i\geq x$。

时间复杂度

我们需要枚举 $i,j,k,l$ 来计算 $f$ 和 $g$，但由于 $kl\leq i\leq n$，因此时间复杂度是 $O(Ln^2\log n)$ 的。

程序

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define ll long long
ll mod;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
const int N=205;
int n,m;
ll fac[N],inv[N],f[N][N],g[N][N],h[N];
inline ll S(int n,int l)
{
	ll sum=inv[l];
	ff(i,0,l) sum=sum*(n+i)%mod;
	return sum;
}
inline void work()
{
	fac[0]=1;
	fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2);
	fd(i,n,1) inv[i-1]=inv[i]*i%mod;
	f[1][0]=1; g[0][0]=1;
	ll t,w;
	fo(k,1,m/2)
	{
		f[1][k]=1;
		fo(j,1,n)
		{
			fd(i,n,1)
			{
				t=w=f[j][k-1];
				for(int l=1;j*l<i;t=t*(w+l)%mod,l++)
					f[i][k]=Add(f[i][k],f[i-j*l][k]*t%mod*inv[l]%mod);
			}
		}
		f[1][k]=0;
		fo(i,0,n) h[i]=0;
		fo(i,0,n) fo(j,0,n-i) h[i+j]=Add(h[i+j],f[j][k]*g[i][k-1]%mod);
		fo(i,0,n) f[i][k]=h[i],g[i][k]=g[i][k-1];
		fo(j,1,n)
		{
			fd(i,n,1)
			{
				t=w=f[j][k-1];
				for(int l=1;j*l<=i;t=t*(w+l)%mod,l++)
					g[i][k]=Add(g[i][k],g[i-j*l][k]*t%mod*inv[l]%mod);
			}
		}
	}
	ll ans=0;
	if(m&1)
	{
		int x=(m-1)/2;
		fo(i,1,n-1)
			if(i<=n-i)
			{
				if(2*i!=n) ans=Add(ans,Mul(f[i][x],f[n-i][x]));
				else ans=Add(ans,S(f[i][x],2));
			}
	}
	else
	{
		int x=m/2;
		ans=f[n][x];
		fo(i,x,n-1) ans=Dec(ans,Mul(f[i][x-1],g[n-i-1][x-1]));
	}
	printf("%lld",ans);
}
int main()
{
	FO(exploit);
	cin>>n>>m>>mod;
	if(m==0) printf("%d",(n==1)%mod);
	else if(m==1) printf("%d",(n==2)%mod);
	else if(m==2) printf("%d",(n>=3)%mod);
	else work();
	return 0;
}