Posted on 2009-11-24 00:03
王之昊 閱讀(584)
評論(2) 編輯 收藏 引用 所屬分類:
數學
感謝AC牛的幫助~~
這道題是說給你一個n, 求有多少棵不同的二叉樹滿足其節點數不超過n.(n <= 100,000 ) 結果太大模上 m (m < 10^9)
我們已經很熟悉節點數為 n 的不同的二叉樹數目是catalan數 Cn. 枚舉每個 Ci % m (0 < i <= n)是顯然的.
但是怎么來算Ci % m 呢?
1 C[i+1] = 2*(2*i+1)/(i+2)*C[i]; 但是m不是素數, 我們怎么處理除法???
2 單獨算 C[i+1]用素因子指數表示的方法（p1^a1 * p2^a2 * ...*pn^an）。可以解決這個問題，但是慢
于是分成兩部分，跟 m 有關的素因子用 2 做， 跟 m 無關的素因子用 1 做，這樣就解決了。