首页 > > 程序设计 > C/C++ >

【zzulioj 2135】这里是天堂！

2018-06-17 22:48:00来源：未知阅读 ()

先考虑当前情况可行与否：

　　如果当a>n或者b>m时是绝对不行的，概率为0；

　　当a+b<m+n时，k一定等于a+b，否则概率为0；

　　当a+b==m+n时，k>=a+n，否则概率为0；

接下来就是求一个概率，考虑到猫猫来到的顺序对答案没有影响，所以可直接使用古典概型，也即求可行的方案数除以总方案数。

可行的方案数为从n里面挑选a个的方案乘上从m里面挑选b个的方案数，总方案数为从m+n里面挑选a+b个的方案数。也即C(n,a)*C(m,b)/C(n+m,a+b)。

由于数据很小，所以可以直接用组合数的递推公式求出答案，然后分别作为分子分母约分一下就可以了。

Description

Maple他打代码打累了，于是Maple跑去找猫猫们来拯救自己。

Maple来到了一个空房间里，房间的隔壁是一个有很多只猫猫的房间，在Maple的房间里有一个按钮，每次按一下按钮，就会有且只有一只猫猫从旁边的房间里跑过来找Maple玩，当然当隔壁房间没有猫的时候并不会有猫猫跑过来。

Maple按了几次按钮后发现跑过来的猫猫只有白色和黄色两种毛色，而且如果假设当每次按按钮后旁边房间剩下的猫跑过来的概率都相同，那么Maple就开始想，如果当隔壁房间共有n只白猫和m只黄猫时，当他按了k次按钮后，跑过来的白猫数量和黄猫数量分别为a只和b只的概率是多少。

Input

第一行有一个整数T，代表有T组数据(1<=T<=2000)

每组数据有五个整数n,m,k,a,b，其中0<=n,m,k,a,b<=10

Output

对于每组数据，得到的概率为一个分数A/B（A<=B且AB为互质整数），输出两个整数A、B，用一个空格分开。

Sample Input

2 1 1 1 1 0 9 1 10 9 1

Sample Output

1 2 1 1

HINT

特殊的，概率为0的分数表示法为0/1。

 1 #include <iostream>
 2 #include<string>
 3 #include<cstring>
 4 #include<vector>
 5 #include<set>
 6 #include<map>
 7 #include<stack>
 8 #include<queue>
 9 #include<list>
10 #include<cmath>
11 #include<algorithm>
12 #include<cstdio>
13 #include <bitset>
14 #include <climits>
15 #include <time.h>
16 #include<iomanip>
17 #define INF 0x3f3f3f3f
18 using namespace std;
19 #define ll long long
20 
21 ll C(int num1,int num2)
22 {
23     if(num2==0) return 1;
24 
25     ll res1 = 1;
26     ll res2 = 1;
27     for(int i=1;i<=num2;i++)
28     {
29         res1*=(num1-i+1);
30         res2*=i;
31     }
32     return res1/res2;
33 }
34 
35 
36 int main()
37 {
38     //freopen("D://in.txt","r",stdin);
39     //freopen("D://out.txt","w",stdout);
40     int T;
41     scanf("%d",&T);
42     while(T--)
43     {
44         int n,m,k,a,b;
45         scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
46         if(a>n||b>m)
47         {
48             printf("0 1\n");
49             continue;
50         }
51         if(a+b<n+m&&k!=a+b)
52         {
53             printf("0 1\n");
54             continue;
55         }
56         if(a+b==n+m&&k<a+b)
57         {
58             printf("0 1\n");
59             continue;
60         }
61         ll res1 = C(n,a)*C(m,b);
62         ll res2 = C(n+m,a+b);
63 
64         ll g = __gcd(res1,res2);
65         res1/=g;
66         res2/=g;
67         printf("%lld %lld\n",res1,res2);
68     }
69     return 0;
70 }