频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
UVA - 10375Choose and divide(数论)
2014-12-03 11:20:57           
收藏   我要投稿

UVA - 10375Choose and pide(数论)

题目链接

题目大意:求 C(p,q) / C(r,s)的值。

解题思路:题目给出公式:那么上面的那个式子就等价于(p!s!(r - s)!)/(q!(p - q)!r!)
需要发现q!和 p!/(P - q)!的关系,枚举1..q的值,可以对应得到p.. p - q + 1,对应乘积就是p!/(p - q)! ,同理s!和(r - s)! / r!也是如此,那么只要边枚举q和s,然后边计算值就可以得到最后的结果,但是枚举的时候应该枚举值小的数,那么如果(p - q)比q小的话,那么就枚举1...(p - q),因为C(p,q) = C(p,p - q)。

代码:

#include 
#include 

using namespace std;

int main () {

    int p, q, r, s;
    while (scanf ("%d%d%d%d", &p, &q, &r, &s) != EOF) {

        q = min (q, p - q);
        s = min (s, r - s);

        double ans = 1.0;
        for (int i = 1; i <= q || i <= s; i++) {
            if (i <= q)
                ans = ans * (p - i + 1) / i;  
            if (i <= s)
                ans = ans * i / (r - i + 1);
        }
        printf ("%.5lf\n", ans);
    }
    return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 数论
上一篇:SPOJ 12943. Counting, dp ,巧妙
下一篇:Number Sequence(杭电1711)(KMP)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站