HardRating 2486

1916. Count Ways to Build Rooms in an Ant Colony

arraymathdynamic-programmingtreedepth-first-searchgraphtopological-sortcombinatorics

解題說明

Count Ways to Build Rooms in an Ant Colony

題目描述：給定一棵有根樹（根為 0），建造房間的順序必須滿足：建造節點 i 之前必須先建造其父節點。求所有合法的建造順序數量，取模 10^9 + 7。

解題思路：問題等價於計算樹的拓撲排序數量。對於每個節點 u，其子樹的建造順序是一個多重集合的交錯排列問題。設 sz[u] 為 u 的子樹大小，則節點 u 的答案為 (sz[u]-1)! / product(sz[child]!) 乘以各子節點的答案。用 DFS 自底向上計算每個子樹大小，利用預先計算的階乘和逆階乘求組合數。

C++ 解法

複雜度分析

時間複雜度：O(n) — DFS 遍歷所有節點，每個節點的處理為 O(子節點數)，總和為 O(n)。

空間複雜度：O(n) — 樹結構、階乘陣列、棧空間。

虛擬碼

1. Build tree from prevRoom array
2. Precompute factorial and inverse factorial
3. DFS post-order to compute subtree sizes
4. For each node u (bottom-up):
   a. ans *= (sz[u]-1)!
   b. For each child c: ans *= inv_fact[sz[c]]
5. Return ans

其他解法

遞迴 DFS：直接用遞迴版 DFS 計算，每個節點回傳 (sz, ways)。邏輯更清晰但可能在深樹上棧溢出。

多項式係數直接計算：將問題看作多項式係數 (sz[u]-1)! / (sz[c1]! × sz[c2]! × ...)，等價於多重集排列公式的樹形推廣。數學上等價但推導方式不同。

延伸思考

若某些節點有額外的先後依賴關係（不僅僅是父子），問題如何變化？
若要輸出字典序最小的合法建造順序，如何修改演算法？
若樹是動態變化的（可以新增/刪除節點），如何即時更新答案？

Count Ways to Build Rooms in an Ant Colony — CaffeCode