take

take
题解参考

题目描述

Kanade has n boxes , the i-th box has p[i] probability to have an
diamond of d[i] size.

At the beginning , Kanade has a diamond of 0 size. She will open the
boxes from 1-st to n-th. When she open a box,if there is a diamond in
it and it's bigger than the diamond of her , she will replace it with
her diamond.

Now you need to calculate the expect number of replacements.

You only need to output the answer module 998244353.

Notice: If x%998244353=y*d %998244353 ,then we denote that
x/y%998244353 =d%998244353

输入描述:
The first line has one integer n.

Then there are n lines. each line has two integers p[i]100 and d[i].
输出描述:
Output the answer module 998244353
示例1
*输入**
复制

3
50 1
50 2
50 3

输出
复制

499122178

备注:

1<= n <= 100000

1<=p[i]*100 <=100

1<=d[i]<=10^9

题意：

有n个箱子，第i个盒子具有p [i]大小为d [i]的钻石的概率。
从1号开始依次打开，如果比手中的宝石大就替换它，计算期望的更换次数
（一开始默认手中钻石为0）

题解：

一旦扯到概率我就感觉好复杂。。。
首先我们要知道期望有可加性的，也就是E(X+Y)=E(X)+E(Y)
所以，所有交换次数的期望就等于每个宝箱打开后交换次数的期望和，而当个宝箱交换次数无非是0或1（即交换与不交换），所以如果一个宝箱能够产生交换次数的话，就会对答案产生贡献了
所以我们就要去看每一个宝箱到底能否做出贡献，这怎么看？交换的情况是当前的宝石更大，但是在此宝箱之前可以有更大的宝石，那我们就要使该宝箱打开后不出现宝石就可以了
总结下，对于每个宝箱，我们使在其之前拥有比当前宝箱更大的钻石的宝箱打开后不出现钻石

式子如图
如果来

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn=1e5+10;
int c[maxn];
struct node
{
    int d,id;
    ll p;
    bool operator<(const node &a)const
    {
        if(d==a.d) return id<a.id;
        return d>a.d;
    }
}q[maxn];

int lowbit(int x)
{
    return x&(-x);
}
void add(int p,ll v)
{
    while(p<=maxn)
    {
        c[p]=(c[p]*v)%mod;
        p+=lowbit(p);
    }
}

ll sum(int p)
{
    ll res=1;
    while(p)
    {
        res=(res*c[p])%mod;
        p-=lowbit(p);
    }
    return res;
}

ll quickpow(ll a,ll b,ll m)
{
    a=a%m;
    ll ans=1;
    while(b)
    {

        if(b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    ll inv=quickpow(100,mod-2,mod);
    for(int i=1;i<=maxn;i++) c[i]=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld %d",&q[i].p,&q[i].d);
        q[i].p=(q[i].p*inv)%mod;
        q[i].id=i;
    }
    sort(q+1,q+n+1);
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+(1LL*sum(q[i].id)*q[i].p%mod))%mod;
        add(q[i].id,(1-q[i].p+mod)%mod);
    }
    printf("%lld\n",ans);
}