牛客多校第五场 F take

链接：https://www.nowcoder.com/acm/contest/143/F
来源：牛客网

题目描述

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

输入例子:

输出例子:

499122178

-->

示例1

输入

复制

输出

复制

499122178

备注:

1<= n <= 100000

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

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

题意：开始手中有一个大小为0的钻石，然后给出n个箱子，有x/100的概率开出y大小的钻石，如果比手中的钻石大的话就交换，求交换次数

思路：这个牵扯到一些数学知识，我们单独算每个箱子得贡献，如果我要交换当前箱子的钻石，说明当前箱子一定要能开出钻石，所以要乘以当前得概率
然后既然当前箱子要交换，说明当前得钻石说明肯定比手中得钻石大，也就是说前面比这个箱子大得钻石都没有开出钻石，也就是要再乘以前面比它大得
钻石得失败概率，比它小的钻石开不开出钻石都不影响当前钻石，所以概率为1
所以每个箱子得贡献为：   比当前钻石大得箱子开钻石失败得概率 * 当前钻石成功概率
但是我们这样取间断的概率有点麻烦，我们这里用树状数组维护前缀积，优化了一下
我们还要注意，我们的数的范围是1e9  但是箱子的个数是1e5,
1e9的数组我们开不了，所以我们需要离散化
还有我们分数取模无法取，所以我们还要使用逆元来计算

下面看代码注释

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define maxn 998244353

using namespace std;

typedef long long ll;

struct sss

{

    ll id,x;

}a[];

ll inv;

ll d[],c[];

ll n,cnt;

ll qpow(ll a,ll n)

{

    ll ans=;

    while(n)

    {

        if(n%) ans=(ans*a)%maxn;

        a=(a*a)%maxn;

        n>>=;

    }

    return ans;

}

ll lowbit(ll x)

{

    return x&(-x);

}

ll sum(ll x)//因为我们要求的是比当前大的钻石概率，而模版树状数组是求小的，我们就反过来即可

{

    ll ans=;

    while(x<=n)

    {

        ans=(ans*c[x])%maxn;

        x+=lowbit(x);

    }

    return ans;

}

void updata(ll x,ll d)//同上

{

    while(x>)

    {

        c[x]=(c[x]*d)%maxn;

        x-=lowbit(x);

    }

}

int main()

{

    scanf("%lld",&n);

    inv=qpow(,maxn-);//计算分母100的逆元

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

    {

        scanf("%lld%lld",&a[i].id,&a[i].x);

        d[i-]=a[i].x;

    }

    sort(d,d+n);//离散化

    cnt=unique(d,d+n)-d;

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

    {

        c[i]=;//初始化前缀积数组

        a[i].x=upper_bound(d,d+cnt,a[i].x)-d+;

    }

    ll ans=;

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

    {

        ans = (ans + (1LL * sum(a[i].x) * a[i].id % maxn * inv)) % maxn;//把前面把他大的箱子的失败概率乘以当前成功的概率

        updata(a[i].x, 1LL * ( - a[i].id)*inv % maxn);//更新树状数组  注意是100-当前概率  因为我们要存的是失败概率

    }

    printf("%lld",ans);

}

秒客网