题解 P4204 【[NOI2006]神奇口袋 】

yybyyb · 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]考虑概率

交换之后考虑概率

因此，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;
}