Bonus Card题解

· · 题解

这么好的题居然没有题解！qwq

先看 Dmitry 参与一类抽选并被选中的概率，答案是 n 轮中每一轮被选中的概率之和。

设计状态 \mathit{f}_{i,j}，

肯定有一位是轮数，另外我们需要知道一类二类各有多少人以及被抽中的概率， 所以 \mathit{f}_{i,j} \Rightarrow 已经进行 i 轮，一类中有 j 个人被选中。

考虑状态转移 \mathit{f}_{i,j}\Rightarrow\mathit{f}_{i+1,j},\mathit{f}_{i+1,j+1} ，

如果下一轮选中的是二类 \mathit{f}_{i,j}：

该状态发生的概率是 \mathit{f}_{i,j}\times ( 二类剩余人数 )/( 总剩余人数 ) ；

如果下一轮选中的是一类 \mathit{f}_{i+1,j+1}：

该状态发生的概率是 \mathit{f}_{i,j} \times ( 一类剩余人数 ) / ( 总剩余人数 ) ；

注意 ：一类被抽中的概率是二类的两倍，使一类权值为 2（ 或者假设有两倍的一类 ） 并且当 Dmitry 作为一类时，分母中加的数也是 2 。

对于具体的统计答案，并不是简单的 n 轮概率之和，而是：假设 Dmitry 是在第 i 轮，作为第 j 个人被抽中的，那么答案应该加上此时符合状态 “经进行 i 轮，一类中有 j 个人被选中” 的概率再除以此时剩余人数。

因为剩下这么多人，只有人数分之一的概率使得被抽中的是 Dmitry。

Code：

//概率DP （看数据范围得知是n方） 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3010;
double n,A,B,f[N][N][2],ans1,ans2;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//其实根本不用快读 
signed main()
{
    n=read(),A=read(),B=read();
//  Dmitry本身不算在 A B 里面 
    if(n>A+B){puts("1.0");puts("1.0");return 0;}
    f[0][0][0]=f[0][0][1]=1;
    for(int i=0;i<n;i++)
    for(int j=0;j<=i&&j<=A;j++)
    {
        if(f[i][j][0]==0) continue;
        if(A-j>0) f[i+1][j+1][0]+=f[i][j][0]*(2*(A-j)/(2*(A-j)+(B-i+j)+2));
        if(B-i+j>0) f[i+1][j][0]+=f[i][j][0]*((B-i+j)/(2*(A-j)+(B-i+j)+2));
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<=i&&j<=A;j++) ans1+=2*f[i][j][0]/(2*(A-j)+(B-i+j)+2); 
    printf("%.16lf\n",ans1);

    for(int i=0;i<n;i++)
    for(int j=0;j<=i&&j<=A;j++)
    {
        if(f[i][j][1]==0) continue;
        if(A-j>0) f[i+1][j+1][1]+=f[i][j][1]*(2*(A-j)/(2*(A-j)+(B-i+j)+1));
        if(B-i+j>0) f[i+1][j][1]+=f[i][j][1]*((B-i+j)/(2*(A-j)+(B-i+j)+1));
    }
    for(int i=0;i<n;i++)
    for(int j=0;j<=i&&j<=A;j++) ans2+=f[i][j][1]/(2*(A-j)+(B-i+j)+1);
    printf("%.16lf\n",ans2);
    return 0;
}

感谢管理员耐心指正（鞠躬orz）