自动搬运

查看原文

来自洛谷，原作者为

	fervency 决不熬夜，除非RE

搬运于2025-08-24 22:25:45，当前版本为作者最后更新于2022-11-09 18:25:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这么好的题居然没有题解！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）