专栏文章

CF1265E题解

PPenguinJ
CF1265E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minxpdlp
此快照首次捕获于
2025/12/02 10:03
3 个月前
此快照最后确认于
2025/12/02 10:03
3 个月前
查看原文
题目。
设 fif_i 表示问完了前 i−1i-1 面镜子，还期望要多少天。
有 fi=pifi+1+(1−pi)f1+1,fn+1=0f_i=p_i f_{i+1}+(1-p_i)f_1 +1,f_{n+1}=0 ，答案即为 f1f_1 。
将递推式变形，有 fi−f1=pi(fi+1−f1)+1f_i-f_1=p_i(f_{i+1}-f_1)+1。
记 gi=fi−f1g_i=f_i-f_1，则 gi=pigi+1+1,gi+1=gi−1pi,g1=f1−f1=0g_i=p_i g_{i+1}+1,g_{i+1}=\frac{g_i-1}{p_i},g_1=f_1-f_1=0。
于是我们可以递推求出所有的 gig_i 。
因为 fn=pnfn+1+(1−pn)f1+1=f1−pnf1+1f_n=p_n f_{n+1}+(1-p_n)f_1+1=f_1-p_n f_1+1，所以 fn−f1=gn=1−pnf1,f1=1−gnpnf_n-f_1=g_n=1-p_n f_1,f_1=\frac{1-g_n}{p_n}。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll n,p[200005],g[200005],ans;
inline ll qpow(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)ret=ret*a%mod;
		a=a*a%mod;
		b>>=1; 
	}
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	g[1]=0;
	for(int i=1;i<=n;i++){
		cin>>p[i];
		p[i]=p[i]*qpow(100,mod-2)%mod;
		g[i+1]=(g[i]-1+mod)%mod*qpow(p[i],mod-2)%mod;
	}
	ans=mod-g[n+1];
	cout<<ans;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...