1 条题解

  • 0
    @ 2025-4-8 14:02:23

    题意分析

    本题要求计算牌局中对手之间持有剩余花色牌的概率。如果你和你的搭档持有某一花色的若干牌时,剩余牌由两个对手分享,在题中给定 aa 张和 bb 张的分法。设剩余的牌总数为 a+ba+b 张,问题变为:

    • 在两位对手各有 13 张牌的前提下,随机发牌中有多少种方法使得在某个花色中,一位对手刚好拿到 aa 张,另一位拿到 bb 张。
    • 与总的可能情况相比,即两对手从剩余 26 张牌中拿出 a+ba+b 张中抽取分布,这样就可以计算出概率。

    利用组合数学的方法计算概率涉及组合数的比值,同时直接计算组合数可能会涉及大数运算,为了避免精度问题,因此需要将相乘相除的计算转化为因数的加减法,利用一个数组存储各因子指数,最后通过循环将指数归零以实现分子分母相消,得到最终的概率。

    解题思路

    1. 构造分数表示式 根据题目需要计算概率值,即

      $$\text{概率} = \frac{\text{符合条件的分布数}}{\text{总的分布数}}. $$

      经过数学推导,可将该比值转化成几个组合数相除的形式。

      组合数 C(n,k)C(n,k) 的计算可写为:

    C(n,k)=n!k!(nk)!.C(n,k) = \frac{n!}{k!(n-k)!}.
    1. 使用数组存放因子指数
      数组 momo 用来存放因子 ii(从 222626)的指数,初始化时先将 221313 的值设为 11(代表分子中因子出现),而 14142626 设为 1-1(代表分母中的因子)。接着根据不同的组合公式需要,对区间 [2,a+b][2,a+b][2,a][2,a][2,b][2,b][2,26ab][2,26-a-b][2,13a][2,13-a][2,26ab(13a)][2,26-a-b-(13-a)] 内的因子指数做相应调整。

    2. 因子约分和计算
      对于每个可能的因子 ii2i262\le i\le 26),使用两个 while 循环:

      • mo[i]<0mo[i] < 0 时,不断将答案除以 ii,同时把 mo[i]mo[i] 增加直到归零。
      • mo[i]>0mo[i] > 0 时,不断将答案乘以 ii,同时将 mo[i]mo[i] 减少直到归零。
        这样得到最终的概率值。
    3. 对称性处理
      由于分布 aabb 在非对称情况下存在两种可能性(即 aa 由对手1得到,bb 由对手2得到,或者反过来),所以如果 aba\neq b,需要将答案乘以 22

    本题代码

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    double solve(int a, int b)
    {
    	double ans = 1.0;
    	int mo[28], i;
    	memset(mo, 0, sizeof(mo));
    	for(i = 2; i <= 13; i++)
    		mo[i] = 1;
    	for(i = 14; i<= 26; i++)
    		mo[i] = -1;
    	for(i = 2; i <= a+b; i++)
    		mo[i]++;
    	for(i = 2; i <= a; i++)
    		mo[i]--;
    	for(i = 2; i <= b; i++)
    		mo[i]--;
    	for(i = 2; i <= 26-a-b; i++)
    		mo[i]++;
    	for(i = 2; i <= 13-a; i++)
    		mo[i]--;
    	for(i = 2; i <= 26-a-b-(13-a); i++)
    		mo[i]--;
     
    	for(i = 2;i <= 26; i++)
    	{
    		while(mo[i] < 0)
    		{
    			ans /= (double)i;
    			mo[i]++;
    		}
    		while(mo[i] > 0)
    		{
    			ans *= (double)i;
    			mo[i]--;
    		}
    	}
    	if(a != b)
    		ans *= 2;
    	return ans;
    }
     
    int main()
    {
    	int a, b;
    	while(scanf("%d%d", &a, &b) && a != -1)
    	{
    		printf("%d-%d split: %.8lf\n",a,b, solve(a, b));
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    1721
    时间
    1000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者