原文链接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 就会交换手中的钻石和箱子里的钻石。
求期望的交换次数。
$1leq nleq 10^5$
题解
我果然好菜啊。
抄了上次 E 题的线段树反而写的恶心了。
考虑期望的线性性,答案相当于 $1 imes $ 与每一个钻石交换的概率 之和。
考虑如何求遇到第 $i$ 个钻石并发生交换的概率。
$P_i=p_i imes prod_limits{j<i,d_jgeq 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; }