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

· · 题解

设女生集合为A。首先先对A集合中的每个Ai的男生集合按编号排序，设A集合中的Ai有m位男生，对于第i位男生：

观察发现是等比数列，套公式得

P=(1-p)^{(i-1)}*(1-(1-p)^{(m*n)})/(1-(1-p)^m)

因为n无限大，所以(1-p)^{(m*n)}无限小。

所以选中i的概率为P=(1-p)^{(i-1)}/(1-(1-p)^m).

接下来只要用权值树状数组维护逆序対即可。

#include<bits/stdc++.h>
using namespace std;
#define N 500100
#define ll long double
int n,m;
ll p,c[N],ans;
int lowbit(int x) {return x&-x;}
void change(int x,ll w)
{
    while(x<N) c[x]+=w,x+=lowbit(x);
}
ll ask(int x)
{
    ll val=0;
    while(x) val+=c[x],x-=lowbit(x);
    return val;
}
vector<int>g[N];
int main()
{
    cin>>n>>m>>p;
    for(int i=1,a,b;i<=m;i++)
      scanf("%d%d",&a,&b),g[a].push_back(b);
    for(int i=1;i<=n;++i) sort(g[i].begin(),g[i].end());
    for(int i=1;i<=n;i++)
    {
        if(!g[i].size()) continue;
        int k=g[i].size(),x;
        for(int j=0;j<k;j++)
        {
            x=g[i][j];
            ll pos=pow(1-p,j)*p/(1-pow(1-p,k));
        //  printf("girl==%d boy==%d p==%Lf\n",i,x,pos);
            ans+=pos*(ask(n)-ask(x));
        }
        for(int j=0;j<k;j++)
        {
            x=g[i][j];
            ll pos=pow(1-p,j)*p/(1-pow(1-p,k));
            change(x,pos);
        }
    }
    printf("%.2Lf",ans);
    return 0;
}