UVA - 10375Choose and divide(数论)

UVA - 10375Choose and divide(数论)

题目链接

题目大意:求 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; }