Wuyanru's blog
0%

[BJ United Round #3] 三色树

发表于 分类于 ，

越来越菜，我该怎么办。

感觉是比较深刻的组合套路，场上不会就等着似掉吧。

题目链接。

题意

对满足如下要求的 个点的无标号无根树计数：

  1. 每一个点有红蓝黄三种颜色之一；
  2. 红色点度数至多为 ，蓝黄点度数至多为 ；
  3. 黄点不与黄点相邻。

，模数为输入的质数。

题解

首先无标号无根树看起来就不好算。

这个时候有一个技巧，就是我们对无标号有根树进行计数。

由于一棵树最多有两个重心（如果有两个，那么这两个重心一定相邻），所以我们令根为中心进行计数。

设 表示一个大小为 的子树，根节点颜色为红／黄／蓝（并且根节点向上有连边），方案数是多少。

先考虑红蓝点的方案数，其对子树根的颜色没有要求，所以一个大小为 的子树为 ，不妨设其为 。

设 表示选了 个子树，总大小为 的方案数，那么 。

不难发现，我们这样会记重，因为我们记的是无根树，子树之间应当是没有顺序的。

那我们改一下状态，设 表示只选择大小 的子树，一共选了 棵，总大小为 ，方案数是多少。

然后按照子树大小 从小到大的顺序加入，假设加入 个大小为 的子树，那么 。

这样就有 和 。 的转移也类似，只是子树的根不能为黄色。

下面是计算答案。因为我们强制令重心为根，所以子树大小一定 。

那么先枚举子树颜色，然后用 转移一下。

不难发现，我们这样没有计算上，有两个点同时为重心的情况。

那么枚举一下这两个点是什么颜色，再加上即可（注意两个点的颜色顺序，以及颜色相同时算重的情况）。

时间复杂度是 。可能需要把数组滚动一下。

代码

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
99
100
101
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
ll g[5][3005];
ll h[5][3005];
ll f[3005][3];
ll vg[6],vh[6];
ll inv[6];
int n,mod;
ll ans;
inline ll qow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
inline ll C(ll a,int b)
{
    ll ans=1;
    for(int i=1;i<=b;i++) ans=ans*(a-i+1)%mod*inv[i]%mod;
    return ans;
}
inline ll get(int col,int lim)
{
    ll ans=0;
    if(col==0) for(int i=0;i<=3;i++) (ans+=g[i][lim])%=mod;
    if(col==1) for(int i=0;i<=2;i++) (ans+=g[i][lim])%=mod;
    if(col==2) for(int i=0;i<=2;i++) (ans+=h[i][lim])%=mod;
    return ans;
}
int main()
{
    n=read(),mod=read();

    f[0][0]=f[0][1]=f[0][2]=1;
    g[0][0]=1,h[0][0]=1;
    for(int i=1;i<=5;i++) inv[i]=qow(i,mod-2);

    int lim=(n-1)/2;
    for(int i=1;i<=lim;i++)
    {
        for(int j=0;j<=3;j++) (f[i][0]+=g[j][i-1])%=mod;
        for(int j=0;j<=2;j++) (f[i][1]+=g[j][i-1])%=mod;
        for(int j=0;j<=2;j++) (f[i][2]+=h[j][i-1])%=mod;

        ll ch=(f[i][0]+f[i][1])%mod,cg=(ch+f[i][2])%mod;
        for(int p=0;p<=4;p++) vg[p]=C(p+cg-1,p),vh[p]=C(p+ch-1,p);
        for(int j=4;j>=0;j--) for(int s=0;s<=n;s++) for(int p=1;p<=j;p++)
        {
            if(s<p*i) continue;
            (g[j][s]+=g[j-p][s-p*i]*vg[p])%=mod;
            (h[j][s]+=h[j-p][s-p*i]*vh[p])%=mod;
        }
    }

    // 假如只有一个点作为重心
    for(int i=0;i<=4;i++) (ans+=g[i][n-1])%=mod;
    for(int i=0;i<=3;i++) (ans+=g[i][n-1])%=mod;
    for(int i=0;i<=3;i++) (ans+=h[i][n-1])%=mod;
    // 假如有两个点作为重心
    if(n%2==0)
    {
        for(int i=0;i<3;i++) for(int j=i;j<3;j++)
        {
            if(i==j&&j==2) break;//不能同时为黄点
            ll v1=get(i,lim),v2=get(j,lim);
            if(i!=j) (ans+=v1*v2)%=mod;
            else (ans+=C(v1+2-1,2))%=mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}