文档章节

[cf 1264 C] Beautiful Mirrors with queries

o
 osc_zoa3moe9
发布于 2019/12/07 20:09
字数 819
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题意:

你有$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=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
 
inline ll power(ll a,ll b){ll ans=1;while(b) ans=(b&1)?ans*a%mod:ans,a=a*a%mod,b>>=1;return ans;}
inline ll inv(ll x){return power(x,mod-2);}
inline ll mo(ll x){return x>=mod?x-mod:x;}
inline ll calc(ll l,ll r){return (mo(ss[r-1]-ss[l-1]+mod)*inv(s[l-1])%mod+1)*inv(s[r]*inv(s[l-1])%mod)%mod;}
 
int main(){
    ll n=read(),q=read(); s[0]=1;
    for(ll i=1;i<=n;i++){
        ll x=read()*inv(100)%mod;
        s[i]=s[i-1]*x%mod,ss[i]=(ss[i-1]+s[i])%mod;
    }
    st.insert(1),st.insert(n+1);
    ll ans=(ss[n-1]+1)%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-1)+mod),ans=mo(ans-calc(x,r-1)+mod),ans=mo(ans+calc(l,r-1)),st.erase(x);
        }
        else{
            int l=*(--it);it++;int r=(*it);//cout<<2<<":"<<l<<" "<<r<<endl;
            ans=mo(ans-calc(l,r-1)+mod),ans=mo(ans+calc(l,x-1)),ans=mo(ans+calc(x,r-1)),st.insert(x);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}
C
o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Codeforces Round #604 (Div. 2)

A. Beautiful String (CF 1265 A) 题目大意 当没有连续两个字母相同时,该字符串为美丽串,给定一个含$a,b,c,?$的字符串,要求将$?$替换成$a$,$b$或$c$,使得该串为美丽串。若无法成为美丽串输...

osc_h9x23mw1
2019/12/06
1
0
Codeforces 1264C/1265E Beautiful Mirrors with queries (概率期望、DP)

题目链接 http://codeforces.com/contest/1264/problem/C 题解 首先显然断点把序列分成几部分,总答案就等于所有部分的答案之和。考虑如何求一部分内的答案。首先有个非常经典的dp是$f_i$表示...

osc_99vlkukb
2019/12/06
1
0
VBoxManage + php5

1.设置网络配置 cf@cf :~$ cat /etc/network/interfaces This file describes the network interfaces available on your system and how to activate them. For more information, see inte......

kenzheng
2015/12/21
31
0
QAQorz的训练记录

感觉还是该从今天开始记下来 5.8日查询 870(查询系统) + 100(洛谷) + 100(牛客) = 1070题, 去重按1000题算 5.8 牛客寒训营 3F 双向搜索+处理前后缀积 牛客寒训营 5G 唯一分解, 埃氏筛法的理解...

osc_k0q149k0
2019/05/08
1
0
linux 命令 草稿

进入vi的命令 http://www.cnblogs.com/88999660/articles/1581524.html vi filename :打开或新建文件,并将光标置于第一行首 vi +n filename :打开文件,并将光标置于第n行首 vi + filenam...

kenzheng
2015/12/18
13
0

没有更多内容

加载失败,请刷新页面

加载更多

使用命名管道承载gRPC

最近GRPC很火,感觉整RPC不用GRPC都快跟不上时髦了。 gRPC设计 gRPC是一种与语言无关的高性能远程过程调用 (RPC) 框架。刚好需要使用一个的RPC应用系统,自然而然就盯上了它,但是它真能够解...

osc_nq69o22c
43分钟前
16
0
06-敏捷开发框架-apis 脚本库 引用位置无关性设计

动态引入技术的设计,对我们来说非常重要。 同时也说明动态语言的使用对我们来说也是非常重要。 没有动态语言的支撑,有些想法可能不容易实现,或者有替代方案,可能会花更大的代价。 前端开...

osc_5zg9z6t1
45分钟前
21
0
(三)学习了解OrchardCore笔记——灵魂中间件ModularTenantContainerMiddleware的第一行①的模块部分

  了解到了OrchardCore主要由两个中间件(ModularTenantContainerMiddleware和ModularTenantRouterMiddleware)构成,下面开始了解ModularTenantContainerMiddleware中间件第一行代码。   ...

osc_kdarxvx0
47分钟前
15
0
50Mn18Cr4V锻锻环件

电机无磁护环怎么锻性能才能《高高》?50Mn18Cr4V高锰无磁钢在变形温度为900~1 100℃、应变速率为0.1 ~10s-1条件下的热变形行为. 结果,VC第二相的应变诱导析出对50Mn18Cr4V的热变形行为产生...

无磁钢
47分钟前
16
0
【遇见offer】一汽-大众实习生专场来啦!成长+学习+福利,一个也不能少~

在上次一汽-大众的社招直播之后,实习生的专场招聘也终于来啦! 针对2020年暑期,我们提供了非常多的实习岗位给大家选择。 如果你想得到大厂实习的宝贵经验,如果你想得到更快速的成长,如果...

osc_b88oux8w
48分钟前
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部