首页 > 其他分享 >[OI] 二项式期望 DP

[OI] 二项式期望 DP

时间:2024-08-22 16:48:59浏览次数:11  
标签:OI qquad OSU times Another 维护 二项式 断点 DP

OSU

OSU

Another OSU

yet Another OSU

yet yet Another OSU

OSU 的题目是这样的:有一些相邻的块,给定每一个块的联通概率,每个连通块对答案有 \(size^{3}\) 的贡献,求总期望

关于此题我曾写过题解 此处

此类题的关键之处在于,当我们设计了一个线性状态 \(f_{i}\) 之后,假如我们基于拼接的思想,尝试维护出来了当前最近的一个连通块个数为 \(x\),其贡献应为 \(x^{3}\),那么现在我们再为其拼接一个块,贡献就会变为 \((x+1)^3\),即 \(x^{3}+3x^{2}+3x+1\),注意到这里还有我们尚未维护的 \(x^{2}\) 与 \(x\) 项,因此我们还需要维护这两种信息才能对 \(x^{3}\),进行转移. 对于 \(x^{2}\) 的维护,显然 \((x+1)^{2}=x^{2}+2x+1\),因此只需要维护 \(x\) 项即可,对于 \(x\) 的维护是显然的

引入两个变量 \(l_{i},s_{i}\),其中 \(f_{i}\) 表示考虑前 \(i\) 个,与 \(i\) 联通的连通块长度,\(s_{i}\) 表示前 \(i\) 个的总得分

容易想到 \(l_{i}\) 的转移:当第 \(i\) 个为断点时将 \(l_{i}\) 置零,否则 \(l_{i}=l_{i-1}+1\)

考虑 \(s_{i}\) 的转移:容易想到,当 \(i\) 为断点时有 \(s_{i}=s_{i-1}\),否则,我们可以得出 \(s_{i-1}=(l_{i-1})^{3}+S\)(其中 \(S\) 是一个之前累积的得分),而 \(s_{i}=(l_{i})^{3}+S\),根据上述 \(l_{i}\) 的转移式我们可以知道 \(l_{i}=l_{i-1}+1\),因而有:

\[s_{i}=(l_{i-1}+1)^{3}+S=(l_{i-1})^3+3(l_{i-1})^{2}+3l_{i-1}+1 \]

因为 \(S\) 不好维护,考虑对两项做差分,消掉 \(S\)

\[s_{i}=s_{i-1}+3(l_{i-1})^{2}+3l_{i-1} \]

因此,我们只需要维护出 \(l_{i}\),即可递推求解 \(s_{i}\)

下面我们来加上概率考虑

期望有一个性质(期望的线性性)\(E(a+b)=E(a)+E(b)\) ,因此有下述转化:

\[E(s_{i})=E(s_{i-1}+3(l_{i-1})^{2}+3l_{i-1})=E(s_{i-1})+3E((l_{i-1})^2)+3E(l_{i-1}) \]

对于 \(i\) 确定为断点的情况,我们有 \(l_{i}=0\),因此 \(E((l_{i-1})^2)=E(l_{i-1})=0\),从而 \(E(s_{i})=E(s_{i-1})\)

否则,对于 \(i\) 确定联通的情况同理,有 \(E(s_{i})=E(s_{i-1})+3(l_{i-1})^{2}+3l_{i-1}\)

否则,对于随机选择的块,直接用上述两种情况乘对应的概率即可,即:

\[E(s_{i})=p_{1}\times E(s_{i-1})+p_{2}\times (E(s_{i-1})+3E(l_{i-1})^{2}+3El_{i-1}) \]

注意到我们还没有维护 \(E(l_{i})\)

对于 \(i\) 确定为断点的情况,\(E(l_{i})=0\)

对于 \(i\) 确定联通的情况,\(E(l_{i})=E_{l_{i-1}+1}=E(l_{i-1})+1\)

否则,按照上述思路,应为

\[E(l_{i})=p_{1}\times 0+p_{2}\times (E(l_{i-1})+1) \]

接着考虑维护 \(E((l_{i})^{2})\)

对于 \(i\) 确定为断点的情况,\(E((l_{i})^{2})=0\)

对于 \(i\) 确定联通的情况,\(E((l_{i})^{2})=E_{(l_{i-1}+1)^{2}}=E((l_{i-1}^{2}+2l_{i-1}+1))=E((l_{i-1}^{2}))+2E(l_{i-1})+1\)

否则,按照上述思路,应为

\[((l_{i})^{2})=p_{1}\times 0+p_{2}\times (E_{(l_{i-1}+1)^{2}}=E((l_{i-1}^{2}+2l_{i-1}+1))=E((l_{i-1}^{2}))+2E(l_{i-1})+1) \]

因为已经维护过了 \(E(l_{i})\),因此至此我们完成了全部变量的维护

#include<bits/stdc++.h>
using namespace std;
int n;
double p[100001],l1[100001],l2[100001],s[100001];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>p[i];
    }
    for(int i=1;i<=n;++i){
        l1[i]=p[i]*(l1[i-1]+1);
        l2[i]=p[i]*(l2[i-1]+2*l1[i-1]+1);
        s[i]=(1-p[i])*s[i-1]+p[i]*(s[i-1]+3*l2[i-1]+3*l1[i-1]+1);
    }
    printf("%.1lf",s[n]);
}

Another OSU

Another OSU

Another Another OSU

yet Another Another OSU

OSU 的 \(k\) 次幂升级版,即贡献变为了 \(x^{k}\)

这一次我们不能再像上述一个一个推式子了,我们需要找一个普遍的规律:

对于刚才的问题我们发现:要想维护一个 \(x^{k}\) 的贡献,显然需要维护 \(k'\in[1,k]\) 的所有 \(x^{k'}\) 的贡献

有二项式定理,即 \((x + y)^n = \sum_{i = 0}^n C_{n}^i x^{n - i} y^{i}\),考虑设 \((f_{i})^{k}\) 为我们对 \(x_{k}\) 项进行的位置为 \(i\) 的转移,效仿刚才的解法,我们会有:

\[(f_{i})^{k}=(f_{i-1}+a)^{k}=\sum_{i = 0}^n C_{n}^i (f_{i-1})^{n - i} a^{i} \]

可以发现在这里实际上用到了全部次数比它低的 \(f_{i}\),因此对于每一个 \(i\),按 \(k\) 从小到大维护即可.

此外,除了用二项式定理求 \(C^{i}_{n}\),还可以用杨辉三角来求系数:

杨辉三角递推式:

\[f_{i,j}=\begin{cases}1\qquad\qquad\qquad\qquad\ j=1\operatorname{or} j=i\\f_{i-1,j-1}+f_{i-1,j}\qquad \operatorname{otherwise}\end{cases} \]

标签:OI,qquad,OSU,times,Another,维护,二项式,断点,DP
From: https://www.cnblogs.com/HaneDaCafe/p/18374059

相关文章

  • NOI2022 众数
    经典题目,对于绝对众数只需要考虑这一个序列的中位数在序列中出现次数是否大于一半即可。这道题用线段树合并维护一下就做完了。点击查看代码#include<bits/stdc++.h>#definefirfirst#definesecsecond#defineintlonglong#definemkp(a,b)make_pair(a,b)usingname......
  • 题解:P10881「KDOI-07」能量场
    \(\text{Link}\)题意给你一个长为\(n\)的序列\(a_{1\dotsn}\),定义一条边\((u,v)\)的权值为\(a_u+a_v\)。对于一张图,定义其权值为包含的所有边的权值乘积。求所有\(n\)个点的有标号基环树的权值之和。对\(998244353\)取模。\(n\le10^3\)。思路非常厉害的题,zky倾......
  • Victor and World(状压DP)
    题目描述Aftertryinghardformanyyears,Victorhasfinallyreceivedapilotlicense.Tohaveacelebration,heintendstobuyhimselfanairplaneandflyaroundtheworld.Thereare\(n\)countriesontheearth,whicharenumberedfrom\(1\)to\(n\)......
  • 洛谷P1540 [NOIP2010 提高组] 机器翻译答案
    #include<bits/stdc++.h>usingnamespacestd;/*数据结构:队列queue 桶:标记某个单词是否出现在内存中 t[i]=false:不在t[i]=true:在对于读入的每个单词x: 如果不存在单词x 存储(入队) t[x]=true 内存中元素个数(q.size())>M: t[q.front()]=falses; ......
  • 浅谈TCP和UDP协议的区别
    **传输模式**TCP协议:数据流(DataStream)--没有消息边界,比如服务端给客户端发来2048字节大小的数据,而客户端设置的一次最大接收大小为1024,这时候就意味着还有1024没能接收过来,要再接收一次。所以容易出现粘包的情况。所谓粘包,就是数据都粘在一起了。UDP协议:数据报(Da......
  • 网络编程UDP、TCP
    1UDP通信客户端UDPClientpublicclassUDPClient{publicstaticvoidmain(String[]args)throwsIOException{//获取本地服务器地址InetAddressserver_address=InetAddress.getLocalHost();//创建数据报套接字以连接到服务器......
  • 免费【2024】springboot 基于Android的个人财务系统的设计与实现
    博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】基于Android的房屋租赁App的设计与实现
    博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】基于Android的房屋租赁App的设计与实现
    博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......
  • 免费【2024】springboot 基于Android的个人财务系统的设计与实现
    博主介绍:✌CSDN新星计划导师、Java领域优质创作者、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行前辈交流✌技术范围:SpringBoot、Vue、SSM、HTML、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数......