并不对劲的bzoj4001:loj2105:p3978:[TJOI2015]概率论

向右看齐 2023-08-17 16:46 71阅读 0赞

##### 题目大意 #####

随机生成一棵\\(n\\)(n\\leq10^9)个节点的有根二叉树，问叶子结点个数的期望。

##### 题解 #####

##### subtask 1：\\(n\\leq100\\)，70pts #####

结论：不同的\\(n\\)个节点的有根二叉树有\\(\\frac\{C\_\{2\\times n\}^\{n\}\}\{n+1\}\\)（也就是卡特兰数）个。  
设\\(f(i)\\)表示\\(i\\)个节点的有根二叉树期望有几个叶子结点。  
计算\\(f(i)\\)时考虑除根以外\\(i-1\\)个节点哪些放左边，哪些放右边。\\(\\Theta(n^2)\\)。

##### subtask 2：\\(n\\leq 10^9\\)，30pts #####

将\\(f(i)\\times \\frac\{C\_\{2\\times n\}^\{n\}\}\{n+1\}\\)打表，得：1,2,6,20,70,252……  
也就是：\\(1\\times 1,2\\times 1,3\\times 2,4\\times 5,5\\times 14,6\\times 42,.....\\)  
有：\\(f(i)\\times \\frac\{C\_\{2\\times n\}^\{n\}\}\{n+1\}=i\\times \\frac\{C\_\{2\\times (n-1)\}^\{n-1\}\}\{n\}\\)  
\\(f(i)=\\frac\{i\\times f(i)\\times \\frac\{C\_\{2\\times (n-1)\}^\{n-1\}\}\{n\}\}\{\\frac\{C\_\{2\\times n\}^\{n\}\}\{n+1\}\}=\\frac\{i\\times(i+1)\}\{2\\times (2\\times i-1)\}\\)

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];~k;k=nxt[k])
    #define LL long long
    #define D double
    using namespace std;
    int read()
    {
        int x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    int n;
    //D g[107],f[107];
    int main()
    {
        n=read();
        /*f[0]=0,g[0]=g[1]=f[1]=1;
        rep(i,2,n)
        {
            rep(j,0,i-1)g[i]+=g[j]*g[i-j-1];
            rep(j,0,i-1)f[i]+=g[j]*g[i-j-1]/g[i]*(f[j]+f[i-j-1]);
        }
        */
        printf("%.9lf",n*(n+1.0)/2.0/(2.0*n-1.0));
        return 0;
    }

##### 一些感想 #####

学习卡特兰数中……

转载于:https://www.cnblogs.com/xzyf/p/11317865.html