自动搬运

查看原文

来自洛谷，原作者为

	yybyyb **

搬运于2025-08-24 21:57:38，当前版本为作者最后更新于2018-04-02 09:51:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑以下性质

$x[1],x[2]..x[n]$等价于$1,2,...n$

证明：

假设取第$k$步以前，所有的球的个数分别是$a[1],a[2]..a[n]$，

球的总数是$sum$

那么，第$k$步取到颜色$y$的概率是$\frac{a[y]}{sum}$

考虑第$k+1$步取到颜色$y$的概率

①第$k$步取了颜色$y$

那么，$k+1$步取到$y$的概率是$\frac{a[y]}{sum}*\frac{a[y]+D}{sum+D}$

②第$k$步没有取到颜色$y$

那么，$k+1$步取到$y$的概率是$\frac{sum-a[y]}{sum}*\frac{a[y]}{sum+D}$

将概率相加，得到第$k+1$步的概率

因此，在没有其他限制下，无论何时取$y$的概率都是相等的 也就是题目中按照$x$排序之后，可以直接将$x$离散。

但是题目中显然存在其他限制，也就是前面的某一次必定会取到某个颜色，所以我们来考虑另外一个性质。

颜色出现的顺序对答案没有影响

对于按照$x$排序之后，相邻的两个$y[i],y[i+1]$

①$y[i]=y[i+1]$，显然没有影响

②$y[i]\neq y[i+1]$考虑概率

交换之后考虑概率

$P1$显然等于$P2$

因此，$y$的出现顺序与结果无关。

根据上面的两个性质，我们可以得出：

1.$x$可以直接离散

2.$y$的顺序对结果并没有影响

因此，我们可以就按照读入顺序处理，并且$x$读进来并没有什么用

记录一下每一个颜色的球个数，以及球的总数

每次要抽到一个颜色的球就给他的数量以及总数都加上$D$ 然后算一下概率就行了

因此范围比较大，概率要用高精度算

为了防止要写高精度除法

可以先分解质因数，然后约掉之后再做乘法就行了。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 1111
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct BigInt
{
	int s[20000],ws;
	void init(){s[1]=1;ws=1;}
	void Multi(int x)
	{
		for(int i=1;i<=ws;++i)s[i]=s[i]*x;
		for(int i=1;i<=ws;++i)s[i+1]+=s[i]/10,s[i]%=10;
		while(s[ws+1])++ws,s[ws+1]=s[ws]/10,s[ws]%=10;
	}
	void output(){for(int i=ws;i;--i)printf("%d",s[i]);}
}Ans1,Ans2;
int pri[20001],tot;
bool zs[20001];
void getpri()
{
	zs[1]=true;
	for(int i=2;i<=20000;++i)
	{
		if(!zs[i])pri[++tot]=i;
		for(int j=1;j<=tot&&i*pri[j]<=20000;++j)
		{
			zs[i*pri[j]]=true;
			if(i%pri[j]==0)break;
		}
	}
}
int Mul[20001],Div[20001];
int sum,a[MAX];
int n,m,D;
void Calc(int x,int *f)
{
	for(int i=1;i<=tot;++i)
		while(x%pri[i]==0)
		{
			f[pri[i]]++;
			x/=pri[i];
		}
}
int main()
{
	n=read();m=read();D=read();
	for(int i=1;i<=n;++i)a[i]=read(),sum+=a[i];
	getpri();
	for(int i=1;i<=m;++i)
	{
		int x=read(),y=read();
		if(!a[y]){puts("0/1");return 0;}
		Calc(a[y],Mul);Calc(sum,Div);
		a[y]+=D;sum+=D;
	}
	for(int i=1;i<=20000;++i)
		if(Div[i]>=Mul[i])Div[i]-=Mul[i],Mul[i]=0;
		else Mul[i]-=Div[i],Div[i]=0;
	Ans1.init();Ans2.init();
	for(int i=1;i<=20000;++i)
		for(int j=1;j<=Mul[i];++j)Ans1.Multi(i);
	for(int i=1;i<=20000;++i)
		for(int j=1;j<=Div[i];++j)Ans2.Multi(i);
	Ans1.output();putchar('/');Ans2.output();puts("");
	return 0;
}