牛客网暑期ACM多校训练营（第五场）：F - take

题意：

Kanade有n个盒子，第i个盒子有p [i]概率有一个d [i]大小的钻石。

起初，Kanade有一颗0号钻石。她将从第1到第n打开盒子。当她打开一个盒子时，如果里面有一颗钻石并且比它的钻石大，那么她将用她的钻石代替它。

现在您需要计算预期的替换次数。

您只需要输出答案模块998244353。

注意：如果x％998244353 = y * d％998244353，那么我们表示x / y％998244353 = d％998244353。

题解：每一个东西对答案的贡献，即这个东西取的概率乘以前面比它大的东西不取的概率。用树状数组维护不取的概率，则每次都能在O(log)的时间取出前面比它大的东西不取的概率。

#include <bits/stdc++.h>

using namespace std;

const int mod = ;

const int maxn = 1e5 + ;

int n;

long long p[maxn], d[maxn];

long long lisan[maxn];

long long bit[maxn];

long long pow_mod(long long x, long long n)

{

    long long ans  = ;

    while(n){

        if(n & ) ans = ans  * x % mod;

        x = x * x % mod;

        n >>= ;

    }

    return ans;

}

long long sum(int i)

{

    long long ans = ;

    while(i){

        ans = ans * bit[i] % mod;

        i -= i & -i;

    }

    return ans;

}

void add(int i, long long x)

{

    while(i <= n){

        bit[i] = bit[i] * x % mod;

        i += i & -i;

    }

}

int main()

{

    long long NY = pow_mod(, mod - );   //求100的逆元

    scanf("%d", &n);

    for(int i = ; i <= n; i++){

        scanf("%lld%lld", &p[i], &d[i]);

        lisan[i] = d[i];    //离散化

        p[i] = p[i] * NY % mod;     //除以100恢复概率

        bit[i] = ;     //树状数组维护乘积需初始化为1

    }

    sort(lisan + , lisan +  + n);

    int li =  unique(lisan + , lisan +  + n) - lisan - 1;

    for(int i = ; i <= n; i++){

        //最后要求比当前数大的概率，即后缀，会有除法，需求逆元，将大小互换，则可优化

        d[i] = li - (lower_bound(lisan + , lisan +  + li, d[i]) - lisan) + ;

    }

    long long ans = ;

    for(int i = ; i <= n; i++){

        ans = (ans + sum(d[i] - ) * p[i]) % mod;

        add(d[i], ( - p[i] + mod) % mod);

    }

    printf("%lld\n", ans);

    return ;

}