牛客网暑期ACM多校训练营（第五场）F题Take题解

考虑每一个东西对答案的贡献，即这个东西取的概率乘以前面比它大的东西不取的概率。

即

代码如下：

#include <bits/stdc++.h>
typedef long long ll;
const int mod = 119 << 23 | 1;
ll Pow(ll a, ll n = mod - 2)
{
    ll t = 1;
    for (; n; n >>= 1, (a *= a) %= mod)
        if (n & 1) (t *= a) %= mod;
    return t;
}
const int N = 1 << 17;
ll bit[N];
void update(int x, ll v)
{
    for (int i = x; i < N; i += i & -i) (bit[i] *= v) %= mod;
}
ll query(int x)
{
    ll t = 1;
    for (int i = x; i; i -= i & -i) (t *= bit[i]) %= mod;
    return t;
}
struct Node
{
    int p, d;
    int id;
    Node() {}
    Node(int p, int d, int id) : p(p), d(d), id(id) {}
    bool operator<(const Node& rhs) const
    {
        return d > rhs.d || d == rhs.d && id < rhs.id;
    }
};
int main()
{
    int n;
    scanf("%d", &n);
    ll inv = Pow(100);
    for (int i = 0; i < N; i++) bit[i] = 1;
    std::vector a(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &a[i].p, &a[i].d);
        a[i].id = i + 1;
    }
    std::sort(a.begin(), a.end());
    ll ans = 0;
    for (auto& t : a)
    {
        ll tmp = (query(t.id - 1) * ((inv * t.p) % mod)) % mod;
        (ans += tmp) %= mod;
        update(t.id, inv * (100 - t.p) % mod);
    }
    printf("%lld\n", ans);
    return 0;
}