The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3219 二项式系数(数论,简单)

之所以要写个解题报告,不是因为这道题很难,而是因为一眼居然没看出来是统计质因数2出现的次数,太nc了,为了把公式记得牢一点,遂写此文~

题目意思很简单,就是让你求组合数C(n,k)是奇数还是偶数。
C(1, 0) = C(1, 1) = 1;
C(n, 0) = 1对于所有n > 0;
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)对于所有0 < kn
对于上述描述,可以直接无视之。。。

由于组合数C(n,k)=         n!
                                    ---------
                                     k!(n-k)!

所以只要算出分子分母中各自包含的质因数2的个数,如果分子的大于分子,就是偶数,反之则是奇数。题目太简单,不过公式很重要,代码就不贴了。

posted on 2009-11-01 01:43 abilitytao 阅读(317) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理