蓝桥杯_堆的计数_动态规划
不太懂
//小根堆==>父亲节总是小于孩子节点
#include <iostream>
#include <cstdio>

using namespace std;
typedef long long LL;
LL d[100005], s[100005], mod = 1000000009;
LL f[100005], inv[100005], n;
LL C(LL n, LL m) {
return f[n] * inv[m] % mod * inv[n - m] % mod;
}
LL qpow(LL a, LL n) {
if (!n || a == 1)return 1;
LL x = qpow(a, n / 2);
return n % 2 ? (x * x % mod * a % mod) : (x * x % mod);
}
int main() {
cin >> n;
f[0] = 1;
for (int i = 1; i < 100005;i++) {
f[i] = f[i - 1] * i % mod;
inv[i] = qpow(f[i], mod - 2);
}
for(int i=n;i>=1;i--)
s[i] = (i * 2 <= n ? s[i * 2] : 0) + ((i * 2 + 1) <= n ? s[i * 2 + 1] : 0) + 1; //c[i]<=n所以不用取余
//初始化子树节点个数
for (int i = 0; i < n+5; i++)d[i] = 1;
for(int i=n;i>=1;i--)if (i * 2 + 1 <= n)
d[i] = ((C(s[i] - 1, s[i * 2 + 1]) * d[i * 2]) % mod * d[i * 2 + 1]) % mod;
cout << d[1] << endl;
}