建设银行网站会员怎么注册,应用软件有哪些,百度seo优化网站怎么做,开一家软件外包公司堆的计数
题目描述
我们知道包含 NN 个元素的堆可以看成是一棵包含 NN 个节点的完全二叉树。
每个节点有一个权值。对于小根堆来说#xff0c;父节点的权值一定小于其子节点的权值。
假设 NN 个节点的权值分别是 1~NN#xff0c;你能求出一共有多少种不同的小根堆吗…堆的计数
题目描述
我们知道包含 NN 个元素的堆可以看成是一棵包含 NN 个节点的完全二叉树。
每个节点有一个权值。对于小根堆来说父节点的权值一定小于其子节点的权值。
假设 NN 个节点的权值分别是 1~NN你能求出一共有多少种不同的小根堆吗
例如对于 NN 4 有如下 3 种
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
由于数量可能超过整型范围你只需要输出结果除以 10991099 的余数。
输入描述
输入输出一个整数 N (1≤N≤105)N (1≤N≤105)。
输出描述
一个整数表示答案。
输入输出样例
示例 输入 4输出 3运行限制
最大运行时间1s最大运行内存: 256M
总通过次数: 372 | 总提交次数: 543 | 通过率: 68.5%
难度: 困难 标签: 2018, 快速幂, 省赛, 动态规划 算法思路
要计算由 1~N 的 N 个不同数字组成的小根堆数量我们需要利用组合数学和动态规划。核心思路是
树形结构完全二叉树的结构固定根节点为最小值 1子树分配剩余 N-1 个数字需要分配到左右子树递归计算每个子树也必须满足小根堆性质组合数学通过组合数计算分配方案利用动态规划避免重复计算
关键公式
对于以节点 i 为根的子树
dp[i] C(size[i]-1, size[left]) × dp[left] × dp[right] mod MOD 其中
size[i]子树 i 的节点数left/right左右子节点C(n,k)组合数表示从 n 个元素选 k 个的方案数
算法演示
以 N4 为例 1 1 1/ \ / \ / \2 3 3 2 2 4/ / /4 4 3
三种不同的小根堆结构均满足父节点 子节点的性质。
代码实现C
#include iostream
#include vector
using namespace std;const long long MOD 1000000009;
const int MAXN 100010;long long fact[MAXN], invFact[MAXN];
int sizes[MAXN];
long long dp[MAXN];// 快速幂计算 a^b mod MOD
long long modExp(long long a, long long b) {long long res 1;while (b) {if (b 1) res (res * a) % MOD;a (a * a) % MOD;b 1;}return res;
}// 预处理阶乘和逆元
void precompute(int n) {fact[0] invFact[0] 1;for (int i 1; i n; i) {fact[i] fact[i-1] * i % MOD;}invFact[n] modExp(fact[n], MOD-2);for (int i n-1; i 1; i--) {invFact[i] invFact[i1] * (i1) % MOD;}
}// 计算组合数 C(n,k) mod MOD
long long nCr(int n, int k) {if (k 0 || k n) return 0;return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD;
}int main() {int N;cin N;// 预处理阶乘和逆元precompute(N);// 计算每个节点的子树大小for (int i N; i 1; i--) {sizes[i] 1;int left 2*i, right 2*i1;if (left N) sizes[i] sizes[left];if (right N) sizes[i] sizes[right];}// 初始化叶子节点的dp值for (int i 1; i N; i) {int left 2*i, right 2*i1;if (left N) dp[i] 1; // 叶子节点}// 动态规划计算dp值从下往上for (int i N; i 1; i--) {int left 2*i, right 2*i1;if (left N) { // 非叶子节点int left_size sizes[left];int right_size (right N) ? sizes[right] : 0;int total sizes[i] - 1;long long comb nCr(total, left_size);dp[i] comb * dp[left] % MOD;if (right N) {dp[i] dp[i] * dp[right] % MOD;}}}cout dp[1] endl;return 0;
}
算法步骤详解 预处理阶乘和逆元 计算 0! 到 N! 的阶乘数组 fact[]通过费马小定理计算阶乘的逆元数组 invFact[]因为 MOD 是质数 计算子树大小 for (int i N; i 1; i--) {sizes[i] 1;if (2*i N) sizes[i] sizes[2*i];if (2*i1 N) sizes[i] sizes[2*i1];
} 从叶子节点向上计算每个节点的子树大小节点 i 的子树大小 1自身 左子树大小 右子树大小 初始化叶子节点 for (int i 1; i N; i) {if (2*i N) dp[i] 1; // 叶子节点方案数为1
} 动态规划计算方案数 for (int i N; i 1; i--) {if (非叶子节点) {int left_size 左子树大小;int total sizes[i]-1; // 需要分配的总节点数long long comb nCr(total, left_size); // 分配方案数dp[i] comb * dp[左子节点] % MOD;dp[i] dp[i] * dp[右子节点] % MOD; // 如果存在}
}
实例验证
输入 N4 时 子树大小计算 节点4size1叶子节点3size1叶子节点2size1 size[4] 2节点1size1 size[2] size[3] 4 DP 计算 dp[4] 1叶子dp[3] 1叶子dp[2] C(1,1) × dp[4] 1×1 1dp[1] C(3,2) × dp[2] × dp[3] 3×1×1 3
输出3 ✓
注意事项 组合数计算 使用预处理的阶乘和逆元保证 O(1) 时间复杂度组合数公式C(n,k)k!(n−k)!n!modMOD 取模运算 所有乘法操作后立即取模防止 long long 溢出使用 (a * b) % MOD 确保中间结果不溢出 遍历顺序 必须从后向前遍历叶子→根确保计算 dp[i] 时子节点的 dp 值已计算完成
测试点设计 边界值测试 N1输出 1单节点堆N2输出 1唯一结构根-左子N3输出 2两种结构根左左/根左右 完全二叉树测试 N7满二叉树输出 80N15满二叉树输出 21964800 性能测试 N10^5在 1s 内完成计算最大组合数计算C(10^5, 50000) mod MOD 取模验证 大 N 结果超过 long long 范围确保所有操作正确取模
优化建议 空间优化 // 使用 vector 替代静态数组
vectorlong long fact(MAXN), invFact(MAXN);
vectorint sizes(MAXN);
vectorlong long dp(MAXN); 组合数计算优化 // 使用卢卡斯定理处理更大的 N
long long lucas(int n, int k) {if (k 0) return 1;return nCr(n % MOD, k % MOD) * lucas(n / MOD, k / MOD) % MOD;
} 并行计算 // OpenMP 并行计算子树大小
#pragma omp parallel for
for (int i N; i 1; i--) {// 计算 sizes[i]
} 记忆化搜索 // 存储已计算的子树方案数
unordered_mapint, long long memo;
if (memo.count(i)) return memo[i];
