take 树状数组+概率统计

题意:
有n个盒子，每个盒子有p概率使得盒子里面有一个大小为d的钻石，每次遇到遇到比你手中更大的钻石你需要进行交换。现在你可以从第1个盒子开始，一直任意选到第n个，求交换次数的期望值是多少。
题解:
每个盒子的概率p的乘100后的值，考虑到大数，就可以考虑用乘法逆元
对于期望高中已学过E(X+Y)=E(X)+E(Y)，过求所以交换次数的期望值就是求各个点的期望值之和。
选到第i个盒子的前提是第1,2,3....i-1的盒子都没有打开，故可以严格按照盒子的下标，对1-p维护一个概率树状数组，需要了解的是概率是相乘，不是相加。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define endl  '\n'
using namespace std;
const int mod=998244353;
ll n,tree[100005];
struct TREE
{
    ll p,d,id;
    bool operator <(const TREE &a)const
    {
        if(d==a.d)return id<a.id;
        return d>a.d;
    }
}a[100005];
void init(ll n)
{
    for(ll i=0;i<=n;i++)
    tree[i]=1;
}
int lowbit(ll x)
{
    return x&-x;
}
void add(ll i,ll x)
{
    while(i<=n)
    {
        tree[i]=(tree[i]*x)%mod;
        i+=lowbit(i);
    }
}
ll sum(ll i)
{
    ll res=1;
    while(i>0)
    {
        res=(tree[i]*res)%mod;
        i-=lowbit(i);
    }
    return res;
}
ll qpow(ll x,ll y,ll mod)
{
    ll res=1;
    while(y)
    {
        if(y&1)res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
      cin>>n;
      init(n);
     ll div=qpow(100,mod-2,mod),ans=0;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i].p>>a[i].d;
        a[i].p=(a[i].p*div+mod)%mod;
        a[i].id=i;
    }
      sort(a+1,a+1+n);
      for(ll i=1;i<=n;i++)
      {
          ans+=(sum(a[i].id)*a[i].p)%mod;
        add(a[i].id,(1-a[i].p+mod)%mod);    
    }
    cout<<(ans+mod)%mod;
    return 0;
}