链接：
https://www.nowcoder.com/discuss/84119
题意：
给定n个箱子， 每个箱子打开发现钻石的概率P（这里的P要除100）， 每个钻石的重量， 有一个人只能持有一个钻石， 每次打开箱子发现手中的钻石小于箱子的钻石， 他就会换掉手中的钻石， 求交换次数的数学期望
分析：
对于一个箱子， 取里面钻石的概率就是（P * （之前不打开比它重的概率））， 那么从最重的钻石开始递推， 用树状数组统计（之前不打开）的概率， 然后把这个点设为不打开。
树状数组一开始初始化为1， 这些箱子起始不打开的概率为1.
#include<bits/stdc++.h>
using namespace std;
const int MOD = ;
const int maxN = 1e6 + ;
int n;
long long c[maxN];
struct box{
long long p, d, index;
bool operator < (const box& a) const{
return d != a.d ? d > a.d : index < a.index;
}
}a[maxN];
long long inv(long long a, long long m){
if(a == ) return ;
return inv(m % a, m) * (m - m / a) % m;
}
int lowbit(int x){
return x & -x;
}
long long sum(int x){
long long ret = ;
while(x > ){
ret *= c[x];
ret %= MOD;
x -= lowbit(x);
}
return ret;
}
void update(int x, int val){
while(x <= n){
c[x] *= val;
c[x] %= MOD;
x += lowbit(x);
}
}
int main(){
// freopen("1.txt","r", stdin);
// freopen("123.txt","w", stdout);
long long INV = inv(, MOD);
scanf("%d", &n);
for(int i = ; i <= n; i++){
c[i - ] = ;
scanf("%lld %lld", &a[i].p, &a[i].d);
a[i].index = i;
}
sort(a + , a + n + );
long long ans = ;
long long temp = ;
for(int i = ; i <= n; i++){
long long p = a[i].p, id = a[i].index;
temp = ((( p * sum(id-) ) % MOD ) * INV) % MOD; //前面不取得概率之积 * 该点的概率
// printf("%lld %lld\n",sum(id - 1), temp);
ans = (ans + temp) % MOD;
update(id, ( - p) * INV % MOD); //把该点更新成不取的
}
printf("%lld\n", ans);
return ;
}