竞赛讨论区 > 牛客网暑期ACM多校训练营(第五场)F题Take题解
头像
你以为你CF过了四题
编辑于 2018-08-02 20:02
+ 关注

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

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


直接暴力计算的复杂度为O(n2)不能接受。我们可以将d从大到小排序,用树状数组维护1 - pi的前缀积。每次插入前查询在它前面比他大的概率的乘积。
(因为从大到小插入了,所以树状数组里面的插入的都是d比他大的。)
由于维护的是乘积,所以我们树状数组要初始化成1。

代码如下:

#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;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐