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