take 树状数组+概率统计

take

https://ac.nowcoder.com/acm/problem/17412

题意:
有n个盒子,每个盒子有p概率使得盒子里面有一个大小为d的钻石,每次遇到遇到比你手中更大的钻石你需要进行交换。现在你可以从第1个盒子开始,一直任意选到第n个,求交换次数的期望值是多少。
题解:
每个盒子的概率p的乘100后的值,考虑到大数,就可以考虑用乘法逆元
对于期望高中已学过E(X+Y)=E(X)+E(Y),过求所以交换次数的期望值就是求各个点的期望值之和。
选到第i个盒子的前提是第1,2,3....i-1的盒子都没有打开,故可以严格按照盒子的下标,对1-p维护一个概率树状数组,需要了解的是概率是相乘,不是相加。

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
#define endl  '\n'
using namespace std;
const int mod=998244353;
ll n,tree[100005];
struct TREE
{
    ll p,d,id;
    bool operator <(const TREE &a)const
    {
        if(d==a.d)return id<a.id;
        return d>a.d;
    }
}a[100005];
void init(ll n)
{
    for(ll i=0;i<=n;i++)
    tree[i]=1;
}
int lowbit(ll x)
{
    return x&-x;
}
void add(ll i,ll x)
{
    while(i<=n)
    {
        tree[i]=(tree[i]*x)%mod;
        i+=lowbit(i);
    }
}
ll sum(ll i)
{
    ll res=1;
    while(i>0)
    {
        res=(tree[i]*res)%mod;
        i-=lowbit(i);
    }
    return res;
}
ll qpow(ll x,ll y,ll mod)
{
    ll res=1;
    while(y)
    {
        if(y&1)res=(res*x)%mod;
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);
      cin>>n;
      init(n);
     ll div=qpow(100,mod-2,mod),ans=0;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i].p>>a[i].d;
        a[i].p=(a[i].p*div+mod)%mod;
        a[i].id=i;
    }
      sort(a+1,a+1+n);
      for(ll i=1;i<=n;i++)
      {
          ans+=(sum(a[i].id)*a[i].p)%mod;
        add(a[i].id,(1-a[i].p+mod)%mod);    
    }
    cout<<(ans+mod)%mod;
    return 0;
}
全部评论

相关推荐

头像
03-14 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
02-13 15:16
三江学院 运营
据说名字越长别人越关注你的昵称我觉得我要被关注了:完全看不出你到底干了什么 全是车轱辘话
点赞 评论 收藏
分享
02-26 13:46
湖南大学 Java
Java抽象小篮子:要用外卖就必须得额外包装下,你这没包装好啊,可以看看我的精品贴子汇总,里面有额外扩展了很多技术亮点的魔改外卖话术,和7000字轮子项目话术
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务