HardRating 2333
1866. Number of Ways to Rearrange Sticks With K Sticks Visible
mathdynamic-programmingcombinatorics
解題說明
Number of Ways to Rearrange Sticks With K Sticks Visible
題目描述： 有 n 根高度各不相同的木棍（高度 1 到 n），排成一列。從左邊看，只有前方沒有更高木棍遮擋的才「可見」。求有多少種排列方式使得恰好有 k 根木棍可見（答案對 10⁹+7 取模）。
解題思路： 此問題與無符號第一類 Stirling 數（Unsigned Stirling Numbers of the First Kind）密切相關。
DP 定義：dp[i][j] = 將 i 根木棍排列使得恰好 j 根可見的方案數。
轉移：考慮最矮的木棍（高度 1）的位置：
- 如果它放在最左邊（一定可見）：剩下 i-1 根木棍需要 j-1 根可見 →
dp[i-1][j-1] - 如果它不放在最左邊：它一定被前面的木棍遮擋（不可見），且它可以放在其餘 i-1 個位置中的任何一個（在某根更高木棍的「後面」） →
(i-1) * dp[i-1][j]
遞推式：dp[i][j] = dp[i-1][j-1] + (i-1) * dp[i-1][j]
基底：dp[0][0] = 1。
C++ 解法
複雜度分析
時間複雜度：O(n × k) — 雙重迴圈，外層 n 次，內層最多 k 次。
空間複雜度：O(k) — 使用一維滾動陣列。
虛擬碼
1. Initialize dp[0..k] = 0, dp[0] = 1
2. For i from 1 to n:
a. For j from min(i, k) down to 1:
- dp[j] = (dp[j-1] + (i-1) * dp[j]) % MOD
b. dp[0] = 0
3. Return dp[k]其他解法
二維 DP O(n × k) 空間：直接維護 dp[i][j] 二維表。邏輯更清晰但空間 O(nk)。
Stirling 數公式：此問題的答案就是無符號第一類 Stirling 數 S(n, k)。可以用生成函數或遞推關係計算，本質上就是上述 DP。理論上也可以用 FFT 加速多項式乘法到 O(n log² n)，但實作複雜度高。
延伸思考
- 無符號第一類 Stirling 數與排列的循環結構有什麼關係？為什麼可見木棍數等於循環數？
- 如果從左右兩邊分別看，限制左邊可見 k1 根、右邊可見 k2 根，方案數如何計算？
- 如果木棍高度可以重複，問題會變成什麼樣？