Chrysanthemum's Blog

我们很容易想到的算法n⁴，枚举任意两个女该，算出她们对答案的贡献，因此再枚举每个人选的男孩，算出选这个男孩的概率，两者相乘就是贡献。选这个男孩的概率，就是这个男孩的概率除以选所有男孩的概率之和。

假如我们现在要求a这个女孩在共n个候选人中选第k个男孩（就是候选人从小到大第k个）的概率。

分子=(1-p)^k-1*p+(1-p)^k-1*p*(1-p)ⁿ+(1-p)^k-1*p*(1-p)²ⁿ+……+(1-p)^k-1*p*(1-p)^oo

=(1-p)^k-1*p*(((1-p)^oo-1)/(-p))

=(1-p)^k-1

多么完美的一个数啊！！

分母=（1-p)⁰+(1-p)¹+(1-p)²+……+(1-p)^n-1

=((1-p)ⁿ-1)/(-p)

这样就求出了第a个女孩选第k个男孩的概率。

有了这些精妙的公式，就很容易优化到了n²。

接下来的优化很明显，先将读入的a排序，再用数据结构（如树状数组，线段树）去维护前缀和就可以了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,sum[500010],cnt,num[500010];
double p,q[500010],tr[500010],ans;
struct node{int a,b;}pai[500010];
bool cmp(const node x,const node y){if (x.a==y.a) return x.b<y.b;return x.a<y.a;}
void add(int x,double val)
{
    while (x<=n)
    {
        tr[x]+=val;
        x+=((x)&(-x));
    }
}
double ask(int x)
{
    if (!x) return 0;
    double ans=0;
    while (x)
    {
        ans+=tr[x];
        x-=((x)&(-x));
    }
    return ans;
}
double ksm(double x,int y)
{
    double ans=1;
    if (!y) return ans;
    while (y)
    {
        if (y&1) ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%lf",&p);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&pai[i].a,&pai[i].b);
        sum[pai[i].a]++;
    }
    sort(pai+1,pai+m+1,cmp);
    for (int i=1;i<=m;i++){if (pai[i].a!=pai[i-1].a) cnt=0;num[i]=++cnt;}
    for (int i=1;i<=n;i++)
    if (sum[i]) q[i]=(ksm(1-p,sum[i])-1)/(-p);
    for (int i=m;i>=1;i--)
    {
        ans+=ksm(1-p,num[i]-1)/q[pai[i].a]*ask(pai[i].b-1);
        add(pai[i].b,ksm(1-p,num[i]-1)/q[pai[i].a]);
    }
    printf("%.2lf\n",ans);
}