题目描述

blablabla

样例

blablabla

算法

(组合数&树形dp) $O(n)$

首先这是一颗完全二叉树,所以给定你节点数量,树的结构就是确定的.那么我们可以算出每个节点的一个子树大小.
其次我们在一个已知大小的树内,得到这个点为根节点的答案,那么这个答案就是左子树的答案乘以右子树的答案然后左右分配这些数ansl乘以ansr乘以C(sz[u]-1,sz[l])然后就完成了.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+9;
const int N=1e5+5;
ll sz[N],ans[N],f[N],ivf[N];//存完全二叉树的子树大小 根节点为u的时候的答案 阶层 阶层的逆元
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    int m=1e5;f[0]=1;
    for(int i=1;i<=m;i++)   f[i]=f[i-1]*i%mod;
    ivf[m]=qp(f[m],mod-2);
    for(int i=m-1;i;i--)    ivf[i]=ivf[i+1]*(i+1)%mod;
}

ll C(ll a,ll b)
{
    return f[a]*ivf[b]%mod*ivf[a-b]%mod;
}

int main()
{
    init();
    ll n;
    scanf("%lld",&n);
    for(int i=n;i>=1;i--)
        sz[i]=(i*2>n?0:sz[i*2])+(i*2+1>n?0:sz[i*2+1])+1;
    for(int i=1;i<=n+1;i++) ans[i]=1;
    for(int i=n;i>=1;i--)
        if(2*i+1<=n)
            ans[i]=C(sz[i]-1,sz[i*2])*ans[i*2]%mod*ans[i*2+1]%mod;
    printf("%lld\n",ans[1]);
    return 0;
}