best coder #35-01<组合数学 || 概率数学>

问题描述

一个盒子里有n个黑球和m个白球。现在DZY每次随机从盒子里取走一个球，取了n+m次后，刚好取完。DZY用这种奇怪的方法生成了一个随机的01串S[1⋯(n+m)]。如果DZY第i次取出的球是黑色的，那么S[i]=1，如果是白色的，那么S[i]=0。

DZY现在想知道，'01'在S串中出现的期望次数。

输入描述

输入有多组测试数据。 (TestCase≤150)

每行两个整数, n, m(1≤n,m≤12)

输出描述

对于每个测试数据，输出一行答案，格式为p/q(p,q互质)。

输入样例

1 1

2 3

输出样例

1/2

6/5

Hint

Case 1: S='01' or S='10', 所以期望次数 = 1/2

Case 2: S='00011' or S='00101' or S='00110' or S='01001' or S='01010'

or S='01100' or S='10001' or S='10010' or S='10100' or S='11000',

所以期望次数 = (1+2+1+2+2+1+1+1+1+0)/10 = 12/10 = 6/5
*************************************************************************************************
本题的官方解释是数学：
第i位上出现0，第i+1位出现1，这种概率是：（m/(n+m)）*（n/(n+m-1)）,0的位置可以出现在第一个一直到倒数第二个；所以累加（n+m-1），相承，公式是n*m/(n+m);

我的做法不是这样，组合数学：
   刚开始看作所有的1发个在最左边，0放在最右边，一共最多有n或m个01串，（个数是其中较小的那个），枚举串的个数从1到最大，当有1
个01串的时候，从n个1中取一个空当，用来插入0，从m个0中可以选1个0放到空档里，也可以选两个一直到选m个，所以对于每一个1都有m种插法，c（n,1）*c(m,1)*1;
    当有两个01串的时候,取1，c（n,2）,取0，第一个1有1到m-1种插法，第二个1有剩余的插法，组合数公式，c(m,2);c(n,2)*c(m,2)*2;
累加下去
总共的排列数就是c(n+m,n);
相比一下，约分，就得到答案了；

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<string>

 #include<cstring>

 #define ll long long

 using namespace std;

 int N,M;

 long long k,t;

 long long zuhe(ll n,ll x)

 {

     ll di=,gao=,ans=;

     for(ll i=;i<=x;i++)

     {

         di*=n;

         n--;

         gao*=i;

     }

     return di/gao;

 }

 void yuefen(ll a,ll b)

 {

     for(ll i=b;i>=;i--)

     {

         if(a%i==&&b%i==)

         {

             k=a/i;

             t=b/i;

             return ;

         }

     }

 }

 int main()

 {

 //    freopen("in","r",stdin);

 //    freopen("out.out","w",stdout);

     while(scanf("%d%d",&N,&M)!=EOF)

     {

         k=;

         t=;

         for(ll i=;i<=N;i++)

         {

             ll temp=;

             if(i>M)

                 break;

             t+=i*zuhe(N,i)*zuhe(M,i);

         }

         k=zuhe(N+M,M);

         yuefen(k,t);

         printf("%I64d/%I64d\n",t,k);

     }

     return ;

 }

巴特西

best coder #35-01<组合数学 || 概率数学>

最新文章

热门文章