分析

题意，给出小顶堆的size，数据从1到size，问可能的小顶堆有几种？

细节

• 两个int相乘不会超过LL，但三个就有可能溢出。
• 这题竟然不用管堆的定义，还是说解法中阴差阳错体现了根比孩子小，搞不清楚。或者，自底向上方法保证了底层是小根堆，推上去就都是小根堆？哪个大佬发发善心，给孩子指条明路吧(~ . ~)
• 快速幂和求阶乘的逆元 具体见 算法基础课常用模板

c++

#include <iostream>
#include <cstdio>

//tools
#define ffor(i,a,b) for(int i=a;i<b;i++)
#define rfor(i,a,b) for(int i=a;i>=b;i--)

using namespace std;


typedef long long LL;
const int N=100010;
const int mod=1e9+9;
LL d[N];//di 第i号节点为根的堆有几种，i=1,2,3、、、
LL s[N];//si 第i号节点为有多少孩子，包括自己
int n;//输入数字个数
int fact[N],infact[N];//阶乘和它的逆元


int qpow(int m,int k,int p=mod){
    //(m^k)mod p
    int ans=1%p;
    while(k){
        if(k&1) ans=(LL)ans*m%p;
        k>>=1;
        m=(LL)m*m%p;
    }
    return ans;
}

int C(int a,int b){
    return (LL)fact[a]*infact[a-b]%mod*infact[b]%mod;
}

void init(){
    fact[0]=1;
    infact[0]=1;    
    ffor(i,1,N){
        fact[i]=(LL)fact[i-1]*i%mod;//阶乘
        infact[i]=(LL)infact[i-1]*qpow(i,mod-2)%mod;
    }

    cin>>n;
}

int main(){
    init();

    //计数i号节点孩子的数量，如果孩子存在加上孩子，最后加上自己
    rfor(i,n,1){
        int l=i*2,r=2*i+1;
        if(l<n+1) s[i]+=s[l];
        if(r<n+1) s[i]+=s[r];
        s[i]++;
    }

    int start=n/2;//第一个非叶子节点
    ffor(i,start,n+1) d[i]=1;

    rfor(i,start,1)
        if(i*2+1<=n)
        d[i]= ((C(s[i]-1,s[i*2+1])*d[i*2])%mod*d[i*2+1])%mod;//乘一次mod一次

    cout<< d[1]<<endl;

    return 0;
}