take 牛客网多校

本文主要是介绍take 牛客网多校，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.nowcoder.com/acm/contest/143/F

第i个钻石被拿<=>[1,i-1]中所有比第i个钻石大的钻石都没被拿 算出这个概率 乘上次数1 就是期望 累加即可

菜的一批

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define M 998244353struct node
{int l;int r;ll val;
};node tree[400010];
ll p[100010];
int d[100010],tmp[100010];
int n,len;ll quickpow(ll a,ll b)
{ll res;res=1;while(b>0){if(b%2) res=(res*a)%M;a=(a*a)%M,b/=2;}return res;
}void pushup(int cur)
{tree[cur].val=(tree[2*cur].val*tree[2*cur+1].val)%M;
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].val=1;if(l==r) return;m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);
}void update(int tar,ll val,int cur)
{if(tree[cur].l==tree[cur].r){tree[cur].val=(tree[cur].val*val)%M;return;}if(tar<=tree[2*cur].r) update(tar,val,2*cur);else update(tar,val,2*cur+1);pushup(cur);
}ll query(int pl,int pr,int cur)
{ll res;if(pl<=tree[cur].l&&tree[cur].r<=pr) return tree[cur].val;res=1;if(pl<=tree[2*cur].r) res=(res*query(pl,pr,2*cur))%M;if(pr>=tree[2*cur+1].l) res=(res*query(pl,pr,2*cur+1))%M;return res;
}int main()
{ll ny,ans,res;int i,pos;scanf("%d",&n);ny=quickpow(100,M-2);for(i=1;i<=n;i++){scanf("%lld%d",&p[i],&d[i]);p[i]=(p[i]*ny)%M;tmp[i]=d[i];}sort(tmp+1,tmp+n+1);len=unique(tmp+1,tmp+n+1)-tmp-1;build(1,len,1);ans=0;for(i=1;i<=n;i++){pos=lower_bound(tmp+1,tmp+len+1,d[i])-tmp;if(pos+1<=len) ans=(ans+(p[i]*query(pos+1,len,1))%M)%M;else ans=(ans+p[i])%M;update(pos,(1-p[i]+M)%M,1);}printf("%lld\n",ans);return 0;
}

 

这篇关于take 牛客网多校的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---