[BZOJ2688]Green Hackenbush

题意: 有$n$棵随机的二叉树，每棵只知道大小为$a_i$

博弈:每次选取一个子树删掉，只剩根不能操作，求先手获胜概率

考虑这个博弈，求出一棵树的$\text{SG}$值

显然有:

1.只有一个点的树的$\text{SG}$值为0

2.多个树组合的问题为$\text{SG}$值异或

暴力$dp$，对于树$T$求答案，设$T$所有可行的后继状态集合为$N(T)$，则得到$\text{SG}$值的表达式为

$\text{SG}(T)=\text{mex}_{R\in N(T)}\lbrace\text{SG(R)}\rbrace $

直接求解复杂度过高，考虑归纳性质

性质:

1.一棵根节点只有一个儿子的树，其$\text{SG}$值为儿子的$\text{SG}$值+1

考虑归纳证明:

设子树为$T$，令$T+u$表示$T$子树上面接上自己作为根，问题变为求证$\text{SG}(T+u)=\text{SG}(T)+1$

设已经归纳证明所有$T$的子联通块成立

我们要求$\text{SG}(T+u)$

$\text{SG}(T+u)=\text{mex} \{\text{SG}(u),\forall _{R\in N(T)}\text{SG}(R+u)\}$

由归纳的性质有

$\forall _{R\subsetneq T}\text{SG}(R+T)=\text{SG}(R)+1$

又因为$\text{SG}(u)=0$，看做把所有儿子的情况平移了1，0的位置由自己占据，因而上式成立

2.多叉树的问题可以归纳为 根分别接上每个儿子得到的树 的问题的组合

因为儿子之间实际互不干扰，比较容易理解

由此得到，一棵树的$\text{SG}$值为其所有儿子的$\text{SG}$值+1的异或和

令$dp_{n,i}$为一棵$n$个节点的二叉树$\text{SG}$值为$i$的概率，为了便于转移，设空树的$\text{SG}$值为-1

考虑直接枚举两棵子树的大小和$\text{SG}$值

考虑对于$n$个节点的二叉树，设其左儿子为$i$时的总概率为$F_i$

得到的$\text{dp}$转移是

$dp_{n,(a+1)\oplus (b+1)}\leftarrow {dp_{i,a}\cdot dp_{n-i-1,b}\cdot F_i}$

我们知道$n$个节点的二叉树方案数为$Catalan(n)=\frac{(2n)!} {n!(n+1)!}$

由此得到$\begin{aligned} F_i=\frac{Catalan(i)Catalan(n-i-1)} {Catalan(n)}\end{aligned} $

此题范围可以直接带入$Catalan(i)$求解，但是依然要提一下递推的做法（似乎精度更有保障?）

$\begin{aligned} F_i=\frac{\frac{(2i)!} {i!(i+1)!}\cdot \frac{(2n-i-2)!} {(n-i-1)!(n-i)!} } {\frac{(2n)} {n!(n+1)!} }\end{aligned} $

递推求解$F_i$，每次$i$改变一阶乘只会改变1或者2，因此由$F_{i-1}$得到$F_i$的递推式为

$F_i=\left\{ \begin{aligned}\frac{n(n+1)} {2n(2n-1)}&& i=0\\ F_{i-1}\cdot \frac{2i(2i-1)} {(i+1)i}\frac{(n-i+1)(n-i)} {2(n-i)(2n-2i-1)} && i\in[1,n-1]\end{aligned}\right.$

化简之后应该是

$F_i=\left\{ \begin{aligned}\frac{(n+1)} {2(2n-1)}&& i=0\\ F_{i-1}\cdot \frac{(2i-1)} {(i+1)}\frac{(n-i+1)} {(2n-2i-1)} && i\in[1,n-1]\end{aligned}\right.$

至此得到一个朴素的$O(n^4)$预处理，由于是异或，可以用$\text{FWT}_{\oplus}$求解，复杂度为$O(n^3)$

对于输入的每棵树，类似背包地叠加概率即可，复杂度为$O(n^3)$

以下是朴素dp代码

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
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=128;

int n;
db dp[N][N];

void FWT(db *a,int f){
	for(int i=1;i<N;i<<=1){
		for(int l=0;l<n;l+=i*2) {
			for(int j=l;j<l+i;j++){
				db t=a[j+i];
				a[j+i]=a[j]-t;
				a[j]+=t;
			}
		}
	}
	if(f==-1) rep(i,0,N-1) a[i]/=N;
}

db F[N],G[N];

int main(){
	dp[0][0]=1,dp[1][0]=1;
	rep(i,2,100) {
		F[0]=1.0/(2*i)/(2*i-1)*(i+1)*i;
		rep(j,1,i-1) {
			F[j]=F[j-1] *  (2*j)*(2*j-1)/(j+1)/j   * 1.0/(2*(i-j))/(2*(i-j)-1)*(i-j+1)*(i-j);
		}
		rep(a,0,i-1) rep(h1,0,N-1) if(dp[a][h1]>0) {
			rep(h2,0,N-1) if(dp[i-a-1][h2]) {
				int nxt=0;
				if(a>0) nxt^=h1+1;
				if(i-1-a>0) nxt^=h2+1;
				dp[i][nxt]+=dp[a][h1]*dp[i-a-1][h2]*F[a];
			}
		}
	}
	n=rd();
	rep(i,0,N-1) F[i]=0;
	F[0]=1;
	rep(i,1,n) {
		int x=rd();
		rep(j,0,N-1) G[j]=0;
		rep(j,0,N-1) if(F[j]) rep(k,0,N-1) G[j^k]+=F[j]*dp[x][k];
		rep(j,0,N-1) F[j]=G[j];
	}
	db ans=0;
	rep(i,1,N-1) ans+=F[i];
	printf("%.6lf\n",ans);
}


以下是FWT优化代码

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
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=128;

int n;
db dp[N][N],T[N][N];

void FWT(db *a,int f){
	for(int i=1;i<N;i<<=1){
		for(int l=0;l<N;l+=i*2) {
			for(int j=l;j<l+i;j++){
				db t=a[j+i];
				a[j+i]=a[j]-t;
				a[j]+=t;
			}
		}
	}
	if(f==-1) rep(i,0,N-1) a[i]/=N;
}

db F[N],G[N];

int main(){
	dp[0][0]=1,dp[1][0]=1;
	T[0][0]=1,T[1][1]=1;
	FWT(T[0],1),FWT(T[1],1);

	rep(i,2,100) {
		F[0]=1.0/(2*i)/(2*i-1)*(i+1)*i;
		rep(j,1,i-1) {
			F[j]=F[j-1] *  (2*j)*(2*j-1)/(j+1)/j   * 1.0/(2*(i-j))/(2*(i-j)-1)*(i-j+1)*(i-j);
		}
		rep(j,0,i-1) rep(k,0,N-1) dp[i][k]+=T[j][k]*T[i-j-1][k]*F[j];
		FWT(dp[i],-1);
		rep(j,0,N-2) T[i][j+1]=dp[i][j];
		FWT(T[i],1);
	}
	n=rd();
	rep(i,0,N-1) F[i]=0;
	F[0]=1;
	rep(i,1,n) {
		int x=rd();
		rep(j,0,N-1) G[j]=0;
		rep(j,0,N-1) if(F[j]) rep(k,0,N-1) G[j^k]+=F[j]*dp[x][k];
		rep(j,0,N-1) F[j]=G[j];
	}
	db ans=0;
	rep(i,1,N-1) ans+=F[i];
	printf("%.6lf\n",ans);
}