看到一篇好的博客特意转出来观摩大佬：转：https://blog.csdn.net/greybtfly/article/details/81413526
题目大意：
给n个箱子排成一排，从头到尾按顺序依次开箱子，第i个箱子都有概率pi开出size为di的钻石。
一开始手中是没有钻石的，如果打开箱子后钻石的size要大于手中的钻石，就丢掉手中的钻石换成箱子中的钻石。
问：丢掉钻石的个数（交换的次数）期望是多少。（有点像狗熊掰棒子，咳咳）
思路：
由概率知识可以知道，选择每个箱子时所有的情况都是独立的（不会的话问高中数学老师不要问我，我也证明不了）
所以期望E=∑（所有箱子打开时交换的期望），由概率论知识，设事件为A，期望为E（A ），发生一次为P（A），发生一次对期望的贡献为F(A)，有E（A）=P(A)*F(A)。本题显然发生一次交换事件对期望的贡献为F(A)=1；所以有
E(A)=P(A);
所以，E=∑(所有箱子打开时交换的期望)=∑( 所有箱子打开时交换的概率)；
然后题目就转化为求箱子打开时发生交换的概率。
我们很容易知道，手中钻石size大小一定是递增的，所以打开第i个箱子时，发生交换的条件是之前没有拿到更大的钻石（如果之前的钻石更大，也就是手中的钻石更大，肯定不能丢掉手中的大钻石，所谓丢了西瓜捡了芝麻....）.
总结一下，之前所有大于它的箱子不能开：1~i-1个箱子中，钻石大于第i个的箱子，不打开的概率的乘积。要发生交换，第i个箱子也得打开，就再乘以pi。
设pi为打开第i个箱子的概率，bi为第i个箱子的钻石大小。
所以 Pi=pi*π(1-pj), j∈{ j是正数|1<=j<=i-1 且 bj>bi };
E=∑ei=∑Pi
期望（数学部分）求解完毕。
但这还没结束。由于结果显然超出了long long 的数据范围，且结果对mod=998244353取余后输出。我们想到同余定理。
(a±b)%mod=(a%mod±b%mod+mod)%mod
a*b*c%mod=a*b%mod*c%mod
但是本题有除法，（因为要除以100）
所以要用到离散数学中的逆元（运算为%mod，要注意mod不同逆元也不同）
设%mod的逆元为inv
有a/b%mod=a*inv%mod (不考虑小数)
求逆元用扩展欧几里得做（听说也有别的方法）。我直接抄板子了，其实我也不清楚求逆元的原理
这还没完
公式中要求前i项大于b的概率连乘积。而n数据范围是1e5.所以，不可能用暴力的方法求解。要用树状数组（或者线段树）
我们离线处理需求，由于我们只需要前i个比当前箱子钻石大的概率连乘积，所以我们将箱子按照钻石大小从大到小排序（要记录好箱子本来的位置，这里可以用离散化O（nlogn），也可以直接保留映射O(n)，我选择第二种）。
按照从大到小的顺序，依次加入树状数组，使用树状数组查询前i个连乘积（注意取模）。
#include<bits/stdc++.h> using namespace std; #define ll long long const ll mod = 998244353; const ll maxn = 4e5+10; ll tree[maxn],n; ll lowbit(ll x) { return x&-x; } void update(ll i , ll x) { while(i<=n) { tree[i]*=x; tree[i]%=mod; i+=lowbit(i); } } ll sum(ll x) { ll Sum=1; while(x>0) { Sum*=tree[x]; Sum%=mod; x-=lowbit(x); } return Sum; } ll inv(ll a , ll m) { if(a==1) return 1; return inv(m%a,m)*(m-m/a)%m; } struct no { ll p,v,i; }co[maxn]; bool cmp(no a , no b) { return a.v>b.v; } int main() { ll imod=inv(100,mod); ll e=0,i,j,k,t; cin>>n; for( i=0 ; i<maxn ; i++) tree[i]=1; for(i=1 ; i<=n ; i++) { scanf("%lld%lld",&co[i].p,&co[i].v); co[i].p*=imod; co[i].p%=mod; co[i].i=i; } sort(co+1,co+1+n,cmp); for(int i=1 ; i<=n ; i++) { e+=sum(co[i].i-1)*co[i].p%mod; e%=mod; update(co[i].i,(1-co[i].p+mod)%mod); } cout<<e<<endl; }