Logs Stacking：木材堆疊圖形計數問題分析

題目要求：已知底層木材數量 n，每層木材數嚴格遞減且每層木材連成一線，求可能的堆疊圖形數量（模 10^5）。

問題本質

這是經典的整數分拆問題，等價於求將 n 表示為嚴格遞減正整數序列和的方案數。即分拆數 q(n)（distinct partitions）。

解題思路

• 動態規劃：dp[i][j] 表示用最大不超過 j 的數拆分 i 的方案數。
• 遞推：dp[i][j] = dp[i][j-1] + dp[i-j][j-1]。
• 因 n ≤ 2×10^9，需用數學公式或生成函數優化，或發現模 10^5 存在週期性。

參考資源

詳細推導與 AC 代碼可參考：CSDN 專欄解析

此題考驗數論與 DP 優化能力，屬於 ACM/ICPC 進階題型。