欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Choose and divide ( 爆long long处理 )

程序员文章站 2022-06-02 12:06:07
...

Choose and divide ( 爆long long处理 )

Choose and divide ( 爆long long处理 )

题意:
给出p,q,r,s;
然后按照所给公式算出C(p,q)和C(r,s);输出C(p,q)/C(r,s);

思路:
首先直接算的话会超出范围;
我们通过看公式可以知道,分子分母个数是一样的;
比如
10! / (5!*(10 - 5)!)那么我们可以选择把5!和10!对消,或者(10 - 5)!和10!对消;反正剩下的个数都是一样的,分子是10*9*8*7*6;分母是5*4*3*2*1;
直接算会超出范围,那么我们就乘一个除一个,但是先算C(p,q)再算C(r,s)还是会超出,所以要把两个一起算.
也就是乘一个p,除一个q,再乘一个s,除一个r;然后p,q,r,s都减减;
但是我一开始的做法是这样从大到小算,一直WA;
后来改成从小到大算就过了也就是先成p-q+i,除以i,再乘i,除以r-s+i,在i++就过了,这点我也想不明白;

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll p,q,s,r;

int main()
{
    while ( cin >> p >> q >> r >> s ) {
        if ( q*2>p ) q = p-q;
        if ( s*2>r ) s=r-s;
        double ans = 1.0;
        ll down1 = 1,down=1;
        for ( ll up1=p-q+1,up=r-s+1; up1<=p||up<=r; up1++,up++ ) {
            if ( up1<=p ) { // 两个c放到一个循环里, 从小到大来
                ans *= up1;
                ans /= 1.0*down1;
            }
            if ( up<=r ) {
                ans *= down;
                ans /= 1.0*up;
            }
            down1 ++; down ++;
        }
        printf("%.5f\n",ans);        
    }

    return 0;
}