题解 P6089 【[JSOI2015]非诚勿扰】

万弘 · 2020-08-10 08:26:40 · 题解

不至于没有题解吧。。。

首先假设一个女性中意 k 个男性，总得先把概率算出来吧。

对于第一个男性，选中的概率 g(1)=P+(1-P)^kP+(1-P)^{2k}P+...
等比数列求和得 g(1)=P\frac{1-(1-P)^\infty}{1-(1-P)^k}=\frac{P}{1-(1-P)^k}

且 \forall i>1,g(i)=g(i-1)\times (1-P)，故可以求出所有 g(i).
从小到大考虑每个女性 i，若选择第 j 个中意的男性(记为 a_{i,j} ),则贡献为

这就是个单点加，询问后缀和。树状数组维护即可。

复杂度 \mathcal O(m\log n)

PS:有点卡精度，我用 double 90pts，long double 就过了

#define MAXN 500011
int n;
struct BIT
{
    long double t[MAXN];
    #define lowb (i&-i)
    void modify(int i,long double k)
    {
        while(i<=n)t[i]+=k,i+=lowb;
    }
    long double Qsum(int i)
    {
        long double res=0;
        while(i)res+=t[i],i-=lowb;
        return res;
    }
}t;
std::vector<int>a[MAXN];
long double Qpow(long double x,int p)
{
    long double res=1;
    while(p)
    {
        if(p&1)res*=x;
        x*=x,p>>=1;
    }
    return res;
}
int main()
{
    n=read();
    int m=read();
    double tmp;
    scanf("%lf",&tmp);
    long double p=tmp,ans=0;
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read();
        a[u].push_back(v);
    }
    for(int u=1;u<=n;++u)
    {
        if(a[u].empty())continue;
        std::sort(a[u].begin(),a[u].end());
        long double now=p/(1-Qpow(1-p,a[u].size()));
        for(int v:a[u])
        {
            ans+=t.Qsum(n-v)*now;
            now*=(1-p);
        }
        now=p/(1-Qpow(1-p,a[u].size()));
        for(int v:a[u])
        {
            t.modify(n-v+1,now);
            now*=(1-p);
        }
    }
    printf("%.2lf",tmp=ans);
    return 0;
}