2018牛客网暑假ACM多校训练赛(第五场)F take 树状数组,期望

时间:2022-09-21 08:47:49

原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-F.html

题目传送门 - https://www.nowcoder.com/acm/contest/143/F

题意

  有 $n$ 个箱子,第 $i$ 个箱子有 $p_i$ 的概率出现大小为 $d_i$ 的钻石。现在 小A 一开始手里有一个大小为 $0$ 的钻石,他会根据 $i$ 从小到大打开箱子,如果箱子里有钻石且比小 A 手中的大,那么小 A 就会交换手中的钻石和箱子里的钻石。

  求期望的交换次数。

  $1\leq n\leq 10^5$

题解

  我果然好菜啊。

  抄了上次 E 题的线段树反而写的恶心了。

  考虑期望的线性性,答案相当于 $1\times $ 与每一个钻石交换的概率 之和。

  考虑如何求遇到第 $i$ 个钻石并发生交换的概率。

  $P_i=p_i\times \prod_\limits{j<i,d_j\geq d_i} (1-p_j)$

  很容易理解这个式子,这里不做解释。

  于是我们只需要树状数组维护一下这个东西就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005,mod=998244353;
int n,d[N],p[N],Ha[N],hs,c[N],ans=0;
int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
void add(int x,int d){
for (x=hs-x+1;x<=hs;x+=x&-x)
c[x]=1LL*c[x]*d%mod;
}
int sum(int x){
int ans=1;
for (x=hs-x+1;x>0;x-=x&-x)
ans=1LL*ans*c[x]%mod;
return ans;
}
int main(){
scanf("%d",&n);
for (int i=1,inv=Pow(100,mod-2);i<=n;i++){
scanf("%d%d",&p[i],&d[i]);
Ha[i]=d[i];
p[i]=1LL*p[i]*inv%mod;
}
sort(Ha+1,Ha+n+1);
hs=unique(Ha+1,Ha+n+1)-Ha-1;
for (int i=1;i<=hs;i++)
c[i]=1;
for (int i=1;i<=n;i++){
d[i]=lower_bound(Ha+1,Ha+hs+1,d[i])-Ha;
ans=(1LL*sum(d[i])*p[i]+ans)%mod;
add(d[i],(1-p[i]+mod)%mod);
}
printf("%d",ans);
return 0;
}