hihoCoder Challenge 31 D - K-Beautiful Tree

题目大意

有$n$个节点,第$i$个点有颜色$c_i$。
定义一棵无根树$T$是$k-$美丽的,当且仅当$T$不存在大于$k$个点的同色联通子图。
现在给定$n,k$以及$\{c_n\}$。请计算所有不同的$k-$美丽带标号无根树的数目。
答案对$10^9+7$取模。

$1\leq k\leq n\leq300$


题目分析

由于我计数水平太低,这题对着题解断断续续搞了好久qwq

首先考虑$k=1$怎么做,即要求所有的同色点不能相邻。
考虑容斥,假设有$x$对同色点相邻容斥系数就是$(-1)^x$。
计算的话就是考虑将点集分成若干个同色连通块再乘上容斥系数。计算分块后的无根树数目,有一个结论就是假设我们分成了$m$个块,大小满足$\sum_{i=1}^ma_i=n$,那么无根树数目就是$n^{m-2}\prod_{i=1}^ma_i$,使用Prüfer序就可以证明。
所以我们只需要dp分组的方案,在dp中带上容斥系数以及$\prod a_i$并记录分组数目就好了。
至于$k>1$的情况,可以发现,假如我们在计算之前先把点集分成一些大小不超过$k$的同色联通块,然后将它们视做单个点,这个容斥依然是正确的(一种合法方案一定由若干个不相邻的极大同色连通块组成)。于是我们相当于要在dp内再套一个分组,这个只需要在前面再跑一个类似的分组dp就好了。
要注意的一点是虽然我们将计算前分好的同色连通块视为一个点做容斥,但是在计算无根树方案的时候节点个数应当是真实的节点个数。
最后时间复杂度是$O(n^3)$的。


代码实现

两层分组嵌套,关系不要写错了qwq

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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int P=1000000007;
const int N=305;
int C[N][N],f[N][N],g[N][N],pw[N][N];
int dp[N],F[N],cnt[N];
int n,K,ans;
inline void update(int &x,int y){(x+=y)%=P;}
inline int sig(int x){return x&1?P-1:1;}
inline int quick_power(int x,int y)
{
int ret=1;
for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
return ret;
}
void pre()
{
C[0][0]=1;
for (int i=1;i<=n;++i)
{
C[i][0]=1;
for (int j=1;j<=i;++j) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
}
for (int i=1;i<=n;++i)
{
pw[i][0]=1;
for (int j=1;j<=n;++j) pw[i][j]=1ll*pw[i][j-1]*i%P;
}
}
void calc()
{
f[0][0]=1;
for (int i=1;i<=n;++i)
for (int j=1;j<=i;++j)
for (int k=1;k<=K&&k<=i;++k)
update(f[i][j],1ll*f[i-k][j-1]*C[i-1][k-1]%P*(k==1?1:pw[k][k-2])%P*k%P);
for (int i=0;i<=n;++i)
{
F[i]=0;
for (int j=0;j<=i;++j) update(F[i],1ll*f[i][j]*sig(j-1)%P*(j>=2?pw[i][j-2]:(j?quick_power(i,P-2):1))%P);
}
g[0][0]=1;
for (int i=1;i<=n;++i)
for (int j=1;j<=i;++j)
for (int k=1;k<=i;++k)
update(g[i][j],1ll*g[i-k][j-1]*C[i-1][k-1]%P*F[k]%P*k%P);
dp[0]=1;
for (int i=1,siz=0;i<=n;++i)
if (cnt[i])
{
siz+=cnt[i];
for (int j=siz;j>=0;--j)
{
dp[j]=1ll*dp[j]*g[cnt[i]][0]%P;
for (int k=1;k<=cnt[i]&&k<=j;++k) update(dp[j],1ll*dp[j-k]*g[cnt[i]][k]%P);
}
}
ans=1ll*dp[1]*quick_power(n,P-2)%P;
for (int i=2;i<=n;++i) update(ans,1ll*dp[i]*pw[n][i-2]%P);
}
int main()
{
freopen("kbtree.in","r",stdin),freopen("kbtree.out","w",stdout);
scanf("%d%d",&n,&K);
for (int i=1,x;i<=n;++i) scanf("%d",&x),++cnt[x];
pre(),calc(),printf("%d\n",ans);
fclose(stdin),fclose(stdout);
return 0;
}