链接 P3830 [SHOI2012]随机树
-
这题好难啊……
-
首先第一问：
-
设(f_i)为有(i)个叶子节点的树的平均深度，(d_i)为任意树的任意一点深度
-
则有(f_i*i)为有(i)个叶子节点的树的深度和
-
随机一次操作所能对平均深度和的贡献都为((d_i+1)*2-d_i)
-
可得：(f_i=f_{i-1}+frac{2}{i})
-
可以看成是新增加了(2)的深度贡献分配在现在的(i)个点上。
-
然后第二问：
-
设(g_{i,j})表示在有(i)个叶子的随机树中，树的深度等于(j)的概率。
-
答案为(sum g_{n,i}*i)
-
然而（
题解说他不好转移）我们发现他不好转移……。 -
改成(f_{i,j})表示在有(i)个叶子的随机树中，树的深度大于等于(j)的概率（猫贼讲过的套路）。
-
显然，对于某一棵随机的，左儿子有(k)个叶子，右儿子有(i−k)个叶子的树，它的深度不小于(j)的概率为
[G_k=f_{k,j-1}+f_{i-k,j-1}-f_{k,j-1}*f_{i-k,j-1}
]
- 这也就是说，事件(a,b)发生的概率(=)事件(a)发生的概率加上事件(b)发生的概率，再减去两个事件同时发生的概率。
- 然后题解说(f_{i,j}=sum frac {G_k}{i-1})…………然而没有证明啊。
- 证明一下：
- 设生成一棵的左儿子恰有(k)个叶子，右儿子有(i-k)个叶子的树的概率为(P_k)
- 那么我们只要证明对于任何(P_k)，均有$$P_k=frac {1}{i-1}$$
- 考虑一棵左儿子有(k)个叶子，右儿子有(i−k)个叶子的树是怎样生成的？
- 相当于你有长度为(i)的序列，每次选择改变左儿子或者右儿子，那么方案数为：
-
[C_{i-2}^{k-1} ]
- 因为第一次一定同时增加了左右子树一个叶子，所以不是(C_{i}^{k})
- 注意操作和操作之间是有区别的，所以操作的方案数乘阶乘，为((i-2)!)。
- 注意这是一个和(k)没有关系的量，即任意(P_k)均相等，所以得证。
- 初始条件(f_{i,0}=1)，表示一定存在深度。
- 注意到答案显然不是(sum f_{n,i}*i)了，考虑怎么算答案。
- 发现(f)实际上就是(g)的前缀和，即(f_{n,i}=sum_{k=i}^{n}g_{n,k})
- 考虑把这个东西写成一个矩阵，(f)的每一项是横着算得，而答案是竖着算得，所以答案就是
-
[sum f_{n,i} ]
#include<bits/stdc++.h>
#define R register int
#define ll long long
#define db double
using namespace std;
const int N=200;
int q,n;db g[N],f[N][N],ans;
void sol1(){
for(R i=2;i<=n;++i)g[i]=g[i-1]+2.0/(db)i;
printf("%.6lf
",g[n]);
}
void sol2(){
for(R i=1;i<=n;++i)f[i][0]=1;
for(R i=2;i<=n;++i)
for(R j=1;j<i;++j){
for(R k=1;k<i;++k)
f[i][j]+=f[k][j-1]+f[i-k][j-1]-f[k][j-1]*f[i-k][j-1];
f[i][j]/=(db)(i-1);
}
// for(R i=1;i<n;++i)printf("f[%d][%d]=%.5lf
",n,i,f[n][i]);
for(R i=1;i<n;++i)ans+=f[n][i];
printf("%.6lf
",ans);
}
int main(){
freopen("s.in","r",stdin);
cin>>q>>n;if(q==1)sol1();else sol2();
return 0;
}