热门
最新
红包
立Flag
投票
同城
我的
发布
ZanderChoo
4 年前
truezanderchoo
啥意思
注册X周年纪念一下
下一条：
蓝桥杯_堆的计数_动态规划不太懂
//小根堆==>父亲节总是小于孩子节点#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;}
立即登录
//小根堆==>父亲节总是小于孩子节点#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;}