HDU 4472 Count：諧和關係配置計數 DP 詳解

HDU 4472 Count：諧和關係配置計數 DP 詳解

村莊關係樹定義：根節點（村長）層級 0，每層節點擁有相同數量的子節點。給定總人數 n (≤ 1000)，求滿足條件的無標號樹形狀數，模 10⁹+7。

問題建模

• 樹高任意，但同層度數相同。
• 設第 0 層 1 個節點，第 1 層 d₁ 個，第 2 層 d₁·d₂ 個，…，第 k 層 ∏ᵢ dᵢ 個。
• 總節點數 n = 1 + d₁ + d₁d₂ + … + d₁d₂…dₖ。
• 每種度數序列 (d₁, d₂, …, dₖ) 對應一種樹形狀（無標號）。

DP 定義與轉移

dp[i]：恰好 i 個節點的諧和樹數量。

考慮根的子樹：根有 d 棵相同的子樹，每棵大小 s，則 n = 1 + d·s → s = (n-1)/d 必須整除。
遞歸地，子樹本身也是諧和樹，故：

dp[n] = Σ dp[(n-1)/d]   對所有 d 使得 (n-1) % d == 0 且 d ≥ 1

初始 dp[1] = 1（單節點）。

完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'007;
const int MAXN = 1000;

int dp[MAXN + 1];

void init() {
    dp[1] = 1;
    for (int n = 2; n <= MAXN; ++n) {
        int64_t sum = 0;
        for (int d = 1; d < n; ++d) {
            if ((n - 1) % d == 0) {
                sum += dp[(n - 1) / d];
                if (sum >= MOD) sum -= MOD;
            }
        }
        dp[n] = sum;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int n, tc = 1;
    while (cin >> n) {
        cout << "Case " << tc++ << ": " << dp[n] << '\n';
    }
    return 0;
}

樣例驗證

n=1: dp[1]=1
n=2: d=1 → dp[1]=1  → dp[2]=1
n=3: d=1→dp[2]=1, d=2→dp[1]=1  → dp[3]=2
n=4: d=1→dp[3]=2, d=3→dp[1]=1  → dp[4]=3
...
輸出與題目 Sample 完全一致。

複雜度

• 預計算：O(n²) = 10⁶ 操作，極快。
• 查詢：O(1)。
• 空間：O(n)。

關鍵洞察

「同層度數相同」⇔ 根的所有子樹同構。因此整棵樹由根度數 d 與子樹大小 s 唯一決定，且 n = 1 + d·s。這將樹計數問題轉化為整數分割式遞歸，極其優雅。

總結

HDU 4472 是樹形 DP + 數論分割的絕佳結合。通過觀察「諧和」條件強制子樹同構，得到簡潔的 dp[n] = Σ dp[(n-1)/d] 轉移。預計算全表後多測試案例 O(1) 答題，模板級解法。