锐客网

  1. 首页 > it技术 > >

CF712E|CF712E Memory and Casinos

设\(f[i]\)为从\(i\)到\(r+1\)且不走出区间的概率
\(f[i]=p[i]f[i+1]+(1-p[i])f[i-1]\)
\(f[i]-f[i-1]=p[i](f[i+1]-f[i-1])\)
\(f[r+1]=1,f[l-1]=0\)
\(g[i]=f[i]-f[i-1]\)
\(g[i]=p[i](g[i+1]+g[i])\)
\(g[i+1]=\frac{1-p[i]}{p[i]} g[i]\)
\(\sum_{i=l}^{r+1} g[i]=f[r+1]-f[l-1]=1\)
\(lis[l][r]=\sum_{i=l}^{r} \prod_{j=l}^i \frac{1-p[j]}{p[j]}\)
\(f[l]=g[l]=\frac{1}{lis[l][r]+1}\)
线段树维护前缀积、前缀和即可

#include"cstdio" #include"cstring" #include"iostream" #include"algorithm" using namespace std; const int MAXN=1<<17; int n,m; int ik[MAXN]; double sum[2][MAXN<<1]; struct rpg{double a,b; }; int read() { int x=0; char ch=getchar(); while(ch<'0'||'9'>1; build(i,l,mid),build(i|1,mid+1,r); return; }void cchg(int k,double v) { sum[0][k]=sum[1][k]=v; k>>=1; while(k){ int i=k<<1; sum[0][k]=sum[0][i]*sum[0][i|1]; sum[1][k]=sum[1][i]+sum[0][i]*sum[1][i|1]; k>>=1; }return; }rpg cask(int k,int l,int r,int le,int ri) { if(le<=l&&r<=ri) return (rpg){sum[0][k],sum[1][k]}; int i=k<<1,mid=l+r>>1; if(le<=mid&&mid

【CF712E|CF712E Memory and Casinos】转载于:https://www.cnblogs.com/AH2002/p/10297729.html

    推荐阅读


    上一篇：python|使用Typescript接口进行运行时JSON类型检查

    下一篇：快到中年的焦虑