take

题目链接

文字转载于

题意:有n个盒子，每个盒子中有p[i]的概率有d[i]大小的钻石，初始有大小为0的钻石，每遇到一个比自己当前大的钻石就要进行交换，求交换的期望。

题解:对于每个钻石进行讨论，这个钻石进行交换的可能性是前面所有比这个大的钻石都不产生且这个钻石产生的概率，那么根据d从大到小进行排序，然后求出每个钻石交换的概率求和即可，还要注意概率是p[i]*100，那么直接乘100的逆元即可，可以用树状数组维护前缀积，维护当前钻石前方比自己大的钻石的不产生的概率的乘积，因为维护乘积所以树状数组要初始化为1.

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;
typedef __int128 LL;

const int maxn = 100000 + 5;
const int Mod = 998244353;

int n,m;

struct Node
{
    ll p,d;
    int id;
    bool operator < (const Node & b) const
    {
        if(b.d == d)    return id < b.id;
        return d > b.d;
    }
}a[maxn];

ll tree[maxn];

inline int lowbit(int x)
{
    return x & (-x);
}

ll quickpow(ll a,int b = Mod - 2)
{
    ll res = 1;
    while(b){
        if(b % 2) res  = (res * a) % Mod;
        a  = (a * a) % Mod;
        b >>= 1;
    }
    return res;
}

void add(int x,ll v)
{  
    for(int i = x; i <= n; i += lowbit(i)){
        tree[i] = (tree[i] * v) % Mod;     
    }
}

ll Query(int x)
{
    ll res  = 1;
    for(int i = x; i > 0; i -= lowbit(i)){
        res = (res * tree[i]) % Mod;
    }
    return res;
}

int main()
{
    for(int i = 0; i <= maxn; i++) tree[i] = 1;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld",&a[i].p,&a[i].d);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    ll ans = 0;
    ll inv = quickpow(100);//求逆元
    for(int i = 1; i <= n; i++){
        Node temp = a[i];
        ll tmp = Query(temp.id - 1) * (inv * temp.p % Mod) % Mod;
        ans  = (ans + tmp) % Mod;
        add(temp.id , inv * (100 - temp.p) % Mod);
    }
    printf("%lld\n",ans);
    return 0;
}

 这里我们要清楚，我们维护的树状数组的下标顺序是按照原来序列的元素顺序进行维护的
而我们是按照d从大到小的顺序进行插入，所以我们每一次插入的都是当前最小值所以我们只需要使它前面所有比它自己大的都不出现，所以才能在这一次交换它，而我们按照从大到小的顺序输入就确保了，当前的数id前面出现的都比它大，所以我们只需要维护不出现概率的和即可，注意：概率的和是用乘法做
因为给出的概率是 *100后的概率，但是期望是要/100后再取余，所以要求100的逆元 逆元的求法