ACM – Uva10375 – 组合数公式

点击量:20

有些匪夷所思的题目。。注释部分加上就WA,不加就AC。。

推公式,因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$
所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。

#include <bits/stdc++.h>
using namespace std;
// 大数,内存处理
#define INF 0x3f3f3f3f
#define ll long long int
#define MEM(a) memset(a, 0, sizeof(a))
#define MEMM(a) memset(a, -1, sizeof(a))
#define DEB(x, n) cout << (x) << " " << (n) << endl
#define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++)
const double PI = acos(-1.0);
#define CR printf("\n")
// 调试用
    template <class Type>
void debug(Type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
int main()
{
#ifdef DEBUG
    freopen("input", "r", stdin);       //从input文件中读入
    // freopen("output", "w", stdout);     //输出到output文件
#endif
    int p, q, r, s;
    double ans = 1.0;
    while(scanf("%d%d%d%d", &p, &q, &r, &s) != EOF)
    {
        ans = 1.0;
        // if(p - q > q) q = p - q;
        // if(r - s > s) s = r - s;
        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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注