题解 P3978 【[TJOI2015]概率论】

· · 题解

这道题可神奇了！

代码只有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))。

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

再设

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=xBA + 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)!)

代码

#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;
}