期望 DP。
定义 \(f_i\) 表示第 \(i\) 个镜子照成功的期望天数,\(p_i\) 为第 \(i\) 天成功的概率,\(q_i\) 为第 \(i\) 天失败的概率。
根据题意容易列出方程:
\[f_i=(f_{i-1}+1)\cdot p_i+(f_{i-1}+1+f_i)\cdot q_i \]移项得:
\[(1-q_i)\cdot f_i=(f_{i-1}+1)\cdot(p_i+q_i) \]同除以 \((1-q_i)\) 得:
\[f_i=\frac{(f_{i-1}+1)\cdot(p_i+q_i)}{1-q_i} \]复杂度 \(O(n\log n)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353;
ll n,f[N],p[N],q[N];
ll ksm(ll x,ll y){
ll res=1;
while(y){
if(y&1)res=res*x%mod;
y>>=1;
x=x*x%mod;
}
return res;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
ll x;cin>>x;
p[i]=x*ksm(100,mod-2)%mod;
q[i]=(1-p[i]+mod)%mod;
}
for(int i=1;i<=n;++i)f[i]=(f[i-1]+1)*(p[i]+q[i])%mod*ksm((1-q[i]+mod)%mod,mod-2)%mod;
cout<<f[n]<<endl;
return 0;
}
标签:res,cdot,题解,ll,int,CF1265E,mod
From: https://www.cnblogs.com/HQJ2007/p/17561354.html