Posted on 2009-11-24 00:03
王之昊 阅读(577)
评论(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 做，这样就解决了。