【BJ United Round3】三色树/【PE677】Coloured Graphs

一道计数好题。

首先考虑一件事,无标号无根树怎么处理。

有个经典的做法就是利用重心,可以强制重心为根,然后减去这些多余情况就好了。由于一棵树可能会有两个重心,那就把连接重心的那条边作为根看就好了。

然后回到这道题,把题目变成无标号有根树。

于是考虑枚举根的颜色和根的度数,然后暴力转移。意思就是,设$R[n][d]$为根颜色为$red$,度数为$d$,有$n$个点的方案数。同理有另外两个。然后转移$d$的时候,就是枚举第一棵子树有几个点,第二棵子树有几个这样,这样做是$O(n^3)$的(因为只有当点为整棵树的根时才用枚举到$4$,否则到$3$就好了)。

发现瓶颈在转移,容易发现这个转移可以容斥,于是复杂度就降到了$O(n^2)$。具体容斥以及转移看代码就好了,虽然我也是看了半天别人代码才懂的。。。

code:

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
//2019.9.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f
#define unl __int128
#define eps 5.6e-8
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define lowbit(x) (x&-x)
#define gc getchar
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline char gc() {
// static char buf[100000],*p1,*p2;
// return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
res s=0,ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline int read() {
// res s=0,ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
inline LL Read() {
RG LL s=0;
res ch=gc();
while(ch<'0'||ch>'9')ch=gc();
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
return s;
}
//inline LL Read() {
// RG LL s=0;
// res ch=gc(),w=1;
// while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=gc();}
// while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
// return s*w;
//}
//inline void write(RG unl x){
// if(x>10)write(x/10);
// putchar(int(x%10)+'0');
//}
inline void swap(res &x,res &y) {
x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//clock_t start=clock();
//inline void ck(){
// if(1.0*(clock()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
const int N=3e3+10;
namespace MAIN{
int kcz;
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:(x<0?x+=kcz:1);
}
inline int Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
inline int mul(const res &x,const res &y){
return int(1LL*x*y%kcz);
}
inline int mul(const res &x,const res &y,const res &d){
return int(1LL*x*y/d%kcz);
}
inline int qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
x=mul(x,x),y>>=1;
}
return ret;
}
int inv[5];
int R[N][5],B[N][4],Y[N][4];
int dp[N],br[N];
int nn;
inline int get(const RG LL &x){
return Add(int(x%kcz),0);
}
inline void DP(const res &n){
if(n==1){
R[1][0]=B[1][0]=Y[1][0]=1;
if(nn>2)br[1]=2,dp[1]=3;
return;
}
//R 1
R[n][1]=dp[n-1];
//R 2
for(res i=1;i+i<=n-1;i++)i==n-1-i?add(R[n][2],mul(dp[i],dp[i]+1,2)):add(R[n][2],mul(dp[i],dp[n-1-i]));
//R 3
res ret=0,val=(n-1)%3?0:dp[(n-1)/3];
for(res i=3;i<=n-1;i++)add(R[n][3],mul(R[i][2],dp[n-i]));
for(res i=1;i+i<n-1;i++)i==n-1-i*2?add(ret,mul(dp[i],dp[i]-1)):add(ret,mul(dp[i],dp[n-1-i*2]));
R[n][3]=Add(int((1LL*mul(get(1LL*R[n][3]-ret*2-val),inv[3])+ret+val)%kcz),0);
//B 1
B[n][1]=dp[n-1];
//B 2
B[n][2]=R[n][2];
//Y 1
Y[n][1]=br[n-1];
//Y 2
for(res i=1;i+i<=n-1;i++)i==n-1-i?add(Y[n][2],mul(br[i],br[i]+1,2)):add(Y[n][2],mul(br[i],br[n-1-i]));
if(n*2<nn)br[n]=int((1LL*R[n][1]+R[n][2]+R[n][3]+B[n][1]+B[n][2])%kcz),dp[n]=int((1LL*br[n]+Y[n][1]+Y[n][2])%kcz);
}
int n;
inline void MAIN(){
nn=n=read(),kcz=read(),inv[0]=inv[1]=1;
if(n==1){puts("3");return;}
if(n==2){puts("5");return;}
for(res i=2;i<=4;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
for(res i=1;i<=n;i++)DP(i);
//R 4
res ret=0,Ret=0,REt=0,val=(n-1)%4?0:dp[(n-1)/4];
for(res i=3;i<n;i++)add(R[n][4],mul(R[i][3],dp[n-i]));
for(res i=1;i*3<n-1;i++)i==n-1-i*3?add(ret,mul(dp[i],dp[i]-1)):add(ret,mul(dp[i],dp[n-1-i*3]));
if(n&1)for(res i=1;i+i<=(n-1)/2;i++)i==(n-1)/2-i?add(Ret,mul(dp[i],dp[i]-1,2)):add(Ret,mul(dp[i],dp[(n-1)/2-i]));
for(res i=1;i+i<=n-3;i++)add(REt,mul(dp[i],R[n-i*2][2]));
add(REt,kcz-(Add(Add(val,ret),Add(Ret,Ret))));
R[n][4]=Add(int((1LL*get(1LL*R[n][4]-val-mul(Add(ret,Ret),2)-mul(REt,3))*inv[4]%kcz+val+ret+Ret+REt)%kcz),0);
//B 3
B[n][3]=R[n][3];
//Y 3
ret=0,val=(n-1)%3?0:br[(n-1)/3];
for(res i=3;i<=n-1;i++)add(Y[n][3],mul(Y[i][2],br[n-i]));
for(res i=1;i+i<n-1;i++)i==n-1-i*2?add(ret,mul(br[i],br[i]-1)):add(ret,mul(br[i],br[n-1-i*2]));
Y[n][3]=Add(int((1LL*get(1LL*Y[n][3]-ret*2-val)*inv[3]%kcz+ret+val)%kcz),0);
res i=n/2;
br[i]=int((1LL*R[i][1]+R[i][2]+R[i][3]+B[i][1]+B[i][2])%kcz),dp[i]=int((1LL*br[i]+Y[i][1]+Y[i][2])%kcz);
dp[n]=int((1LL*R[n][2]+R[n][3]+B[n][2]+Y[n][2])%kcz);
res ans=Add(Add(dp[n],R[n][4]),Add(B[n][3],Y[n][3]));
if(n%2==0)add(ans,Add(mul(dp[n/2],br[n/2]),kcz-mul(br[n/2],br[n/2]-1,2)));
printf("%d\n",ans);
}
}
int main(){
// srand(19260817);
// freopen("signin.in","r",stdin);
// freopen("signin.out","w",stdout);
MAIN::MAIN();
return 0;
}