smzx 进球数 题解

· · 题解

这题数据范围很小，只有 18 个时间片，所以可以枚举恒大和国安的进球数（范围为 [0,18]）。只要其中一方进球数是质数，就是合法方案，累加到概率。

接下来考虑如何计算概率。我们假设当前枚举到的是恒大进球 i 个，国安进球 j 个。

再把恒大进球 i 个的概率记为 hd_i，国安进球 j 个的概率记为 ga_i。那么恒大进球 i 个并且国安进球 j 个的情况概率为恒大进球 i 个的概率乘国安进球 j 个的概率，即 hd_i\times ga_i。

再考虑如何求 hd_i 和 ga_i。因为恒大进球 i 个，所以恒大有 18-i 个时间片没进球。又知恒大进球概率为 A\% ，可得恒大不进球概率为 1-A\%。由于恒大在哪些时间片进球我们是不确定的，但我们知道恒大进球的时间片是 18 个中的 i 个，可能的情况为 C^i_{18} 个。最后整合到一起可以得出 hd_i=C^i_{18}(A\%)^i(1-A\%)^{18-i}。ga_i 同理。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=30;
int r;
double a,b,ans,hd[N],ga[N],dp[N][N];
bool check(int x)//判断质数
{
    if(x<2) return false;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}
int main()
{
    scanf("%d",&r);
    for(int i=0;i<=18;i++)//预处理，用杨辉三角求组合数
    {
        dp[i][0]=1;
        for(int j=1;j<=i;j++) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
    }
    while(r--)
    {
        ans=0;
        scanf("%lf%lf",&a,&b);
        for(int i=0;i<=18;i++)//求出hd[i]和ga[i]
        {
            hd[i]=ga[i]=dp[18][i];
            for(int j=1;j<=i;j++) hd[i]*=a/100.0,ga[i]*=b/100.0;
            for(int j=1;j<=18-i;j++) hd[i]*=(1-a/100.0),ga[i]*=(1-b/100.0);
            //printf("%d:%lf %lf\n",i,hd[i],ga[i]);
        }
        for(int i=0;i<=18;i++)//枚举恒大进球数
        {
            for(int j=0;j<=18;j++)//枚举国安进球数
            {
                if(check(i)||check(j)) ans+=hd[i]*ga[j];//进球数有质数
            }
        }
        printf("%lf\n",ans);
    }
    return 0;
}