专栏文章

题解 P3978 【[TJOI2015]概率论】

UUnknown_Error
P3978题解参与者 70已保存评论 82

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
82 条
当前快照
1 份
快照标识符
@mkdsqrgh
此快照首次捕获于
2026/01/14 17:06
2 个月前
此快照最后确认于
2026/01/14 17:06
2 个月前
查看原文

这道题可神奇了！

代码只有8行（包含include，using...，return 0）

首先，这是一道数学题

设g[x] 为 节点数是 x 的二叉树有多少种，显然枚举根的左右子树可以得到:

g[x] = Σ g[i] * g[x-i-1] 。特殊的，这里g[0]=1，表示空子树。

可以发现这是一个卡特兰数的表示，所以直接得到通项:

g[x] = (2x)!/(x!x!(x+1))。

CPP
   我们还可以设 多项式A = Σx^i * g[i] ，那么显然 A=x*A^2 + 1，我们解一下多项式之后发现它的闭形式为 (1-sqrt(1-4x))/2x。另一个根因为不收敛所以被舍去了。

再设

CPP
f[i] 为i节点数为i的二叉树的叶子数的期望(显然 f[0]=0,f[1]=1)，那么

f[x] = Σ (f[i] + f[x-i-1]) * g[i] * g[x-i-1] /g[x] = 2*Σ f[i] * g[i] * g[x-i-1] /g[x]

所以 g[x] * f[x] = 2Σ f[i] * g[i] * g[x-i-1],我们就再设h[i] = f[i] * g[i] (显然h[0]=0,h[1]=1),设多项式B = Σx^i * h[i] 。那么可以得到: B=xB*A + x,然后解一下多项式可以得到 B = x * (1-4x)^(-1/2)。 其实我们可以先求 C = (1-4x)^(-1/2) ，然后把它右移一位就是B。 也就是我们如果相求B中n次项前的系数的话，求一下C中的第n-1项就行了。 解C的话，我们套用一下 广义二项式定理

可以得到

C(n) = (-1/2)(-1/2 - 1)(-1/2 - 2)....(-1/2 - n+1)/ n! *(-4)^n 。

强行化简一波发现上式 = (2n)!/(n!n!)
所以

B(n) = (2n-2)!/((n-1)!(n-1)!)

代码

CPP
#include<bits/stdc++.h>
using namespace std;
double a;
int main(){
  cin>>a;
  printf("%.11lf\n",a*(a+1)/(2*(2*a-1)));
  return 0;
}

评论

共 82 条评论，欢迎与作者交流。

正在加载评论...