[CF1265E] Beautiful Mirrors with queries
题意
●有 \(n\) 个关卡，每关有 \(p_i\) 的通过概率，通过进下一关，没通过从最近的存档点重新开始。
●关卡 \(1\) 默认为存档点，会有 \(q\) 次修改，每次修改一个关卡是否为存档点的设置，并询问对应的期望通关步数。
分析
我们先考虑一个简化版的问题，即 CF1265E。题意只有 \(1\) 为存档点，没有修改。我们考虑这道题的做法，不如设 \(f_i\)表示通过关卡 \(i\) 的期望步数，显然我们有 \(f_{i}=f{i-1}+1+(1-p_i)·f_{i}\) 即通过该关卡成功及失败情况步数和，解得 \(f_i=\frac{f_{i-1}+1}{p_i}\)。直接递推+逆元就可以求得本题解。
那么考虑这道题我们首先可以找一些优雅的规律，首先对于上一题，我们可以手推发现一些规律。
\(f_1= \frac {1}{p_1}，f_2=\frac{1}{p_2}+\frac{1}{p_1p_2}，f_3=\frac{1}{p_3}+\frac{1}{p_2p_3}+\frac{1}{p_1p_2p_3}...\)。
于是我们不妨设从 \(l\) 走到 \(r\) 的期望步数为 \(g(l,r)=\frac {1}{p_{r-1}}+\frac {1}{p_{r-1}p_{r-2}}+...+\frac{1}{p_{r-1}p_{r-2}...{p_l}}\)。
我们考虑找寻一种方法维护所有存档点，以及两个相邻存档点的距离。
我们考虑两个存档点 \(l,r\) 中间加入一个新存档点 \(x\) 的情况，我们不妨最先把 \(1\) 和 \(n+1\) 丢进 set 中（因为最开始考虑就是从 \(1\) 走到 \(n+1\)的情况）。
而后我们使用 set 查找目前最近的 \(l,r\) 存档点。
代码如下
l=*--_set.lower_bound(x),r=*_set.upper_bound(x);
而后我们依照题意考虑如下情况
- 若 \(x\) 原本不是存档点，则一段 \(g(l,r)\) 会被修改为 \(g(l,x)+g(x,r)-g(l,r)\)。
- 若 \(x\) 是存档点，则一段 \(g(l,r)\) 会被修改为 \(-g(l,x)-g(x,r)+g(l,r)\)。
则我们考虑复杂度瓶颈，即快速计算形如上面那式子。
我们考虑维护一个形如后缀积的东西，设它为 \(edf_i=\frac{1}{p_ip_{i+1}p_{i+1}...p_{n}}\)，我们易有 \(edf_r·g(l,r)=edf_{r-1}+edf_{r-2}+...+edf{i}\)。那么我们显然可以考虑使用前缀和维护形如后面区间和的 \(edf\)，我们有令 \(sum_i=\sum_{j=1}^{i}edf_i\)，这样的话我们就可以使用前缀和维护出 \(g(l,r)=\frac{sum_{r-1}-sum_{i-1}}{edf_{r}}\)。那么我们考虑 \(O(n)\) 预处理前缀和和类后缀积数组就可以 \(O(1)\) 求得答案。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;
const int N=1e6+7;
int edf[N],sum[N];
int p[N];
const int mod=998244353;
struct node{
int inv[2000100],fac[2000100];
int qpow(int shu,int cifang){
int ans=1;int k=cifang;
while(k){
if(k&1){ans=ans*shu%mod;ans%=mod;shu=shu*shu%mod;shu%=mod;}
else{shu=shu*shu%mod;shu%=mod;}
k>>=1;
}
return ans%mod;
}
void init(int len){
fac[0]=1;
for(int i=1;i<=len;i++) fac[i]=fac[i-1]*i%mod;
inv[len]=qpow(fac[len],mod-2);
for(int i=len;i;i--){
inv[i-1]=inv[i]*(i)%mod;
}
}
int C(int n,int m){
return fac[n]%mod*inv[m]%mod*inv[n-m]%mod;
}
int _inv(int x){
return qpow(x,mod-2);
}
}lg_get;
int calc(int l,int r){
return ((sum[r-2]-sum[l-1]+mod)%mod*lg_get._inv(edf[l-1])+1)%mod*edf[l-1]%mod*lg_get._inv(edf[r-1])%mod;
}
set<int> _set;
signed main(){
cin>>n>>q;
edf[0]=1;
int inv100=lg_get._inv(100);
for(int i=1;i<=n;i++){
scanf("%lld",&p[i]);
p[i]=p[i]*inv100%mod;
edf[i]=edf[i-1]*p[i]%mod;
sum[i]=sum[i-1]+edf[i];
sum[i]%=mod;
}
_set.insert(1),_set.insert(n+1);
int ans=calc(1,n+1);
int x;
while(q--){
scanf("%lld",&x);
int l=*--_set.lower_bound(x),r=*_set.upper_bound(x);
if(_set.count(x)){
ans=ans-calc(l,x)-calc(x,r)+calc(l,r),_set.erase(x);
ans%=mod;ans+=mod;ans%=mod;
}
else{
ans=ans+calc(l,x)+calc(x,r)-calc(l,r),_set.insert(x);
ans%=mod;ans+=mod;ans%=mod;
}
printf("%lld\n",ans%mod);
}
return 0;
}