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