[cf 1264 C] Beautiful Mirrors with queries
题意:
你有$n$个魔镜,第$i$个魔镜有$p_{i}$的概率说你美。
从第1天开始,你会依次询问魔镜$1-n$你美不美。
若第$i$个魔镜说你美则你明天会继续询问第$i+1$个魔镜。
否则你明天会从该魔镜前面第一个复活点魔镜开始询问。初始时只有魔镜1是复活点。
当第$n$个魔镜说你美的时候你会开心的一批。
现在有$q$次操作,每次操作修改一个魔镜使其成为/不成为复活点。
每次操作之后请你求出期望多少天你能开心的一批。
$n,q\leq 2\times 10^{5}$。
题解:推出一段区间答案的简单表示形式即可。
一开始想复杂了,用期望的线性性推了个式子发现做不了。
实际上我们只需要根据最简单的思路推式子即可。
设$E_{i}$为从$i$走到$n$的期望天数。
则有$E_{i}=p_{i}\times(1+E_{i+1})+(1-p_{i})\times(1+E_{1})$。
手动消元一下$E_{1}$,得到$E_{1}=\frac{1}{p_{n}}+\frac{1}{p_{n}p_{n-1}}+\cdots +\frac{1}{p_{n}p_{n-1}\cdots p_{1}}$。
那么考虑复活点这件事,容易发现整个序列被复活点分成了若干个区间。
每个区间是独立的。即$ans=\sum{E_{[f_{i-1},f_{i}]}}$。
那么我们考虑$E_{[l,r]}$如何计算。
推广上面那个式子,得到$E_{[l,r]}=\frac{1}{p_{r}}+\frac{1}{p_{r}p_{r-1}}+\cdots +\frac{1}{p_{r}p_{r-1}\cdots p_{l}}$。
我们设$s_{i}$为$p_{1}p_{2}\cdots p_{i}$,那么有
$E_{[l,r]}=\frac{(p_{r-1}p_{r-2}\cdots p_{l}+p_{r-2}p_{r-3}\cdots p_{l}+\cdots +p_{l}+1)}{\frac{s_{r}}{s_{l-1}}}$。
我们再设$ss_{i}=s_{1}+s_{2}+\cdots +s_{i}$,那么有
$E_{[l,r]}=\frac{\frac{(ss_{r-1}-ss_{l-1})}{s_{l-1}}+1}{\frac{s_{r}}{s_{l-1}}}$。
于是只需要用一个$set$维护复活点即可做到$O(nlogn)$。
代码:
#include<bits/stdc++.h>
#define maxn 200005
#define maxm 500005
#define inf 0x7fffffff
#define mod 998244353
#define ll long long
#define debug(x) cerr<<#x<<": "<<x<<endl
#define fgx cerr<<"--------------"<<endl
#define dgx cerr<<"=============="<<endl using namespace std;
ll s[maxn],ss[maxn];
set<int> st; inline ll read(){
ll x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
} inline ll power(ll a,ll b){ll ans=;while(b) ans=(b&)?ans*a%mod:ans,a=a*a%mod,b>>=;return ans;}
inline ll inv(ll x){return power(x,mod-);}
inline ll mo(ll x){return x>=mod?x-mod:x;}
inline ll calc(ll l,ll r){return (mo(ss[r-]-ss[l-]+mod)*inv(s[l-])%mod+)*inv(s[r]*inv(s[l-])%mod)%mod;} int main(){
ll n=read(),q=read(); s[]=;
for(ll i=;i<=n;i++){
ll x=read()*inv()%mod;
s[i]=s[i-]*x%mod,ss[i]=(ss[i-]+s[i])%mod;
}
st.insert(),st.insert(n+);
ll ans=(ss[n-]+)%mod*inv(s[n])%mod;
while(q--){
int x=read();
set<int>::iterator it=st.lower_bound(x);
if(*it==x){
int l=*(--it);it++;int r=(*(++it));//cout<<1<<":"<<l<<" "<<r<<endl;
ans=mo(ans-calc(l,x-)+mod),ans=mo(ans-calc(x,r-)+mod),ans=mo(ans+calc(l,r-)),st.erase(x);
}
else{
int l=*(--it);it++;int r=(*it);//cout<<2<<":"<<l<<" "<<r<<endl;
ans=mo(ans-calc(l,r-)+mod),ans=mo(ans+calc(l,x-)),ans=mo(ans+calc(x,r-)),st.insert(x);
}
printf("%I64d\n",ans);
}
return ;
}
C
最新文章
- 监控Linux系统性能的工具--nmon(一)
- msbuild ConfuserEx.Build 加密
- AI图片剪切
- alpha发布之小组评论
- 黑马程序员——JAVA基础之简述集合collection
- 关于Windows下mysql忘记root密码的解决方法
- ES 中的那些坑
- MLlib-聚类
- 项目管理模式之如何去除SVN标记
- [工作] 使在家办公(Work From Home)更有效率的建议
- Spring 拦截器实现事物
- xml解析总结-常用需掌握
- JS 字符串对象 数组对象 函数对象 函数作用域
- MySql共享锁和排它锁
- oracle 定时 job
- 在redis中使用lua脚本
- js数组去重与性能分析(时间复杂度很重要)
- Nginx 504 Gateway Time-out问题解决
- 解决dpdk中出现IOMMU not found的问题
- [java]Stream API——collect、reduce、orElse(x)