堆的計數
題目描述
我們知道包含?NN?個元素的堆可以看成是一棵包含?NN?個節點的完全二叉樹。
每個節點有一個權值。對于小根堆來說，父節點的權值一定小于其子節點的權值。
假設?NN?個節點的權值分別是 1~NN，你能求出一共有多少種不同的小根堆嗎？
例如對于?NN?= 4 有如下 3 種：
1
/ \
2 3
/
4
1
/ \
3 2
/
4
1
/ \
2 4
/
3
由于數量可能超過整型范圍，你只需要輸出結果除以?109+9109+9?的余數。
輸入描述
輸入輸出一個整數?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 個的方案數
算法演示
以 N=4 為例：
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[i+1] * (i+1) % 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*i+1;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*i+1;if (left > N) dp[i] = 1; // 葉子節點}// 動態規劃計算dp值（從下往上）for (int i = N; i >= 1; i--) {int left = 2*i, right = 2*i+1;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*i+1 <= N) sizes[i] += sizes[2*i+1]; }- 從葉子節點向上計算每個節點的子樹大小
- 節點 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; // 如果存在} }
實例驗證
??輸入 N=4 時：??
-
子樹大小計算：
- 節點4：size=1（葉子）
- 節點3：size=1（葉子）
- 節點2：size=1 + size[4] = 2
- 節點1：size=1 + size[2] + size[3] = 4
-
DP 計算：
- dp[4] = 1（葉子）
- dp[3] = 1（葉子）
- dp[2] = C(1,1) × dp[4] = 1×1 = 1
- dp[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 值已計算完成
測試點設計
-
??邊界值測試??
- N=1：輸出 1（單節點堆）
- N=2：輸出 1（唯一結構：根-左子）
- N=3：輸出 2（兩種結構：根+左左/根+左右）
-
??完全二叉樹測試??
- N=7（滿二叉樹）：輸出 80
- N=15（滿二叉樹）：輸出 21964800
-
??性能測試??
- N=10^5：在 1s 內完成計算
- 最大組合數計算：C(10^5, 50000) mod MOD
-
??取模驗證??
- 大 N 結果超過 long long 范圍
- 確保所有操作正確取模
優化建議
-
??空間優化??
// 使用 vector 替代靜態數組 vector<long long> fact(MAXN), invFact(MAXN); vector<int> sizes(MAXN); vector<long 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_map<int, long long> memo; if (memo.count(i)) return memo[i];
簡易開發環境)
